DSA problem
All Nodes Distance K in Binary Tree
Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node. You can return the answer in any order. Distance is measured along tree edges and is symmetric (a parent is distance 1 from its child, just as a child is distance 1 from its parent).
The complication is that a binary tree provides downward links (left, right) but not upward links to the parent — yet a node at distance k from the target can lie above, below, or to the side of the target. We need to be able to walk upward from the target as well as downward.
The standard trick is a two-phase algorithm. Phase 1 is a DFS that builds an explicit parent map: a hashmap from each node to its parent. This converts the tree into a general (now undirected) graph in which we can navigate in any direction. Phase 2 is a BFS or DFS from target that uses three neighbors per node — left child, right child, and parent (if any) — together with a visited set so we never revisit a node. After exactly k BFS layers, every node in the current frontier is at distance k from the target.
Time and space are both O(n): each node and each edge are visited a constant number of times in both phases, and the parent map plus visited set use linear memory.
Examples
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2[7,4,1]root = [1], target = 1, k = 3[]root = [0,1,null,3,2], target = 2, k = 1[1]Constraints
- The number of nodes in the tree is in the range [1, 500].
- 0 <= Node.val <= 500
- All the values Node.val are unique.
- target is the value of one of the nodes in the tree.
- 0 <= k <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.