All Nodes Distance K in Binary Tree
Return the values of all nodes exactly k edges away from a target node, by adding parent links and running a level-by-level BFS from the target.
Problem Understanding
All Nodes Distance K in Binary Tree: given the root of a binary tree with unique values, a target node, and an integer k, return the values of all nodes that are exactly k edges from the target, in any order.
Examples: [3,5,1,6,2,0,8,null,null,7,4], target 5, k 2 → [7,4,1]; [1], target 1, k 3 → [].
The Intuition: Turn the Tree Into a Graph
Distance in a tree can run up through ancestors, so think of it as an undirected graph:
- Add parent links with one DFS, the same traversal as in Maximum Depth of Binary Tree.
- BFS from the target, one level per unit of distance, exactly like Binary Tree Level Order Traversal but starting mid-tree.
- Never revisit a node, so the walk only moves outward.
- After k levels, the queue is the answer.
The outward rings around a start node are the same idea as Rotting Oranges on a grid.
Interactive Walkthrough
TARGET 5 · k = 2 · d = DISTANCE FROM TARGET
RECORD PARENTS
distance
:
k away
:
queue
Empty
A DFS records each node's parent, so every node can step up as well as down: 9 nodes, now an undirected graph
Next
Start the BFS at the target 5, distance 0
root
target
k
Each node is labeled with its distance from the target once reached. The node being expanded is filled and the links it crosses, including upward ones, are solid. Try From a leaf to see the search climb.
Dry Run Table
Input: [3,5,1,6,2,0,8,null,null,7,4], target 5, k = 2.
| Distance | Expand | New nodes | Queue |
|---|---|---|---|
| 0 | [5] | ||
| 1 | 5 | 6, 2, 3 (parent) | [6, 2, 3] |
| 2 | 6, 2, 3 | 7, 4 from 2; 1 from 3 | [7, 4, 1] |
Answer: [7,4,1].
The Solution Template
One DFS for parents, k rounds of BFS. The C version uses arrays indexed by value, since LeetCode values are unique and at most 500.
All Nodes Distance K in Binary Tree Code
1var distanceK = function(root, target, k) {2 const parent = new Map();3 const dfs = (node, par) => {4 if (!node) return;5 parent.set(node, par);6 dfs(node.left, node);7 dfs(node.right, node);8 };9 dfs(root, null);10 let queue = [target];11 const seen = new Set(queue);12 for (let d = 0; d < k; d++) {13 const next = [];14 for (const node of queue) {15 for (const nb of [node.left, node.right, parent.get(node)]) {16 if (nb && !seen.has(nb)) {17 seen.add(nb);18 next.push(nb);19 }20 }21 }22 queue = next;23 }24 return queue.map((node) => node.val);25};
Edge Cases & Common Mistakes
- k = 0: the answer is the target itself.
- k larger than the tree: the queue empties and the answer is
[]. - Forgetting the seen set: parent links make every edge two-way, so the BFS would walk back.
- Only searching below the target: nodes above it and in sibling subtrees are missed.
- Target is the root: its parent is null, which the neighbor check skips.
Summary
Map every node to its parent with a DFS, then BFS from the target over left, right and parent links for k levels, skipping seen nodes. The final queue is the answer. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet