Print all nodes at a distance of K in BT
HardAdd parent pointers, then BFS outward
Problem
Return all node values that are exactly distance k from a target node in a binary tree.
Add parent pointers so the tree acts like a graph, then BFS k steps out from the target.
The idea
Distance in a tree can go upward as well as down, so first map every node to its parent, then run a BFS from the target treating parent, left and right as neighbours. After k levels the queue holds the answer.
The trick
- One pass to record parents, then a normal BFS.
- A visited set is essential or you will walk back down where you came from.
- O(n) time and space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — root, target=5, k=2 Values: 5, 2.
1record parent pointers via BFS/DFS2BFS from target over left,right,parent for k levels3collect nodes at level kInput
- array
- [5, 2]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
- Output:
- [1, 4, 7]
- Explanation:
- Nodes exactly 2 edges from node 5.
Example 2
- Input:
- tree = [1,2,3], target = 1, k = 1
- Output:
- [2, 3]
- Explanation:
- The two children.
Example 3
- Input:
- tree = [1], target = 1, k = 0
- Output:
- [1]
- Explanation:
- Distance 0 is the node itself.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.