All Nodes Distance K in Binary Tree
Find every node exactly k edges away from a target in a binary tree, including nodes reached by going up. Add parent links, then run a breadth-first search. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given the root of a binary tree, the value target of one of its nodes, and an integer k. Return the values of all nodes that are exactly k edges away from the target node.
Distance counts edges in either direction: a path may go up from a node to its parent as well as down to its children. Every value in the tree is unique, so target identifies exactly one node, and that node is always present.
The tree is given in level order, with null marking a missing child. Return the values in any order.
Example 1
- Input
- root = [8, 3, 12, 1, 6, null, 15, null, null, 4, 7], target = 6, k = 2
- Output
- [1, 8]
From 6, one step up reaches 3. One more step reaches 3's other child, 1, and 3's parent, 8. The children of 6 (4 and 7) are only 1 step away.
Example 2
- Input
- root = [8, 3, 12, 1, 6, null, 15, null, null, 4, 7], target = 15, k = 4
- Output
- [1, 6]
The path goes 15 → 12 → 8 → 3, and the fourth step reaches 3's children.
Example 3
- Input
- root = [8, 3, 12, 1, 6, null, 15, null, null, 4, 7], target = 3, k = 0
- Output
- [3]
The only node at distance 0 is the target itself.
Constraints
- The number of nodes is in the range [1, 500].
- 0 ≤ Node.val ≤ 500, and all values are unique.
- target is the value of a node in the tree.
- 0 ≤ k ≤ 1000
Practice
Runs 14 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked All Nodes Distance K in Binary Tree in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve All Nodes Distance K in Binary Tree
Pattern: Tree to graph + BFS
If the target were the root, this would be "list the nodes at depth k", a plain level-order walk. The difficulty is that answers can also lie above the target or in a sibling subtree, and tree nodes only point down.
Once you notice that "distance in edges, in any direction" is a graph question, the fix is clear: give every node a link to its parent, so each node has up to three neighbors (left, right, parent). Now the tree is an undirected graph, and the nodes exactly k steps away are the k-th layer of a breadth-first search from the target. A visited set stops the search from walking back the way it came.
Approach 1: Distance from every node via root paths
Record the path from the root to the target. For each other node, find its path from the root, locate the lowest common ancestor with the target, and add the two depths below it. Correct, but finding paths for every node repeats work.
Time O(n · h) · Space O(n)
Approach 2: Climb ancestors, search down
Walk from the target up through its ancestors. For the ancestor at distance d, collect nodes at depth k - d in its other subtree (the one not containing the target), plus the ancestor itself when d == k. Linear and memory-light, but the "other subtree" bookkeeping is fiddly to get right under pressure.
Time O(n) · Space O(h)
Approach 3: Parent map + BFS from the target
- Traverse the tree once, storing
parent[node]for every node and remembering the node whose value istarget. - BFS from the target node with a visited set. Each step expands to left child, right child and parent.
- After exactly
krounds, the nodes left in the queue are the answer. If the queue empties first, return an empty list.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Distance from every node via root paths | O(n · h) | O(n) |
| Climb ancestors, search down | O(n) | O(h) |
| Parent map + BFS from the target | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
All Nodes Distance K in Binary Tree solution in Python
from collections import deque
def distance_k(root: Optional[TreeNode], target: int, k: int) -> list[int]:
parent = {root: None}
start = None
stack = [root]
while stack: # record parents and find the target node
node = stack.pop()
if node.val == target:
start = node
for child in (node.left, node.right):
if child:
parent[child] = node
stack.append(child)
queue = deque([start])
seen = {start}
for _ in range(k):
if not queue:
return []
for _ in range(len(queue)):
node = queue.popleft()
for nxt in (node.left, node.right, parent[node]):
if nxt and nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return [node.val for node in queue]All Nodes Distance K in Binary Tree solution in JavaScript
function distanceK(root, target, k) {
const parent = new Map([[root, null]]);
let start = null;
const stack = [root];
while (stack.length) {
// record parents and find the target node
const node = stack.pop();
if (node.val === target) start = node;
for (const child of [node.left, node.right]) {
if (child) {
parent.set(child, node);
stack.push(child);
}
}
}
let queue = [start];
const seen = new Set([start]);
for (let step = 0; step < k && queue.length; step++) {
const next = [];
for (const node of queue) {
for (const nb of [node.left, node.right, parent.get(node)]) {
if (nb && !seen.has(nb)) {
seen.add(nb);
next.push(nb);
}
}
}
queue = next;
}
return queue.map((node) => node.val);
}Common mistakes
- Only searching down from the target and missing nodes reached through its parent.
- Forgetting the visited set, so BFS goes from a child to its parent and back again, reporting nodes at the wrong distance.
- Not handling k larger than the tree's diameter. The queue empties and the answer should be an empty list, not an error.
- Treating k = 0 as a special case and forgetting to return the target itself.
What interviewers look for
Say the reframing early: "parent links turn this into an undirected graph, and the answer is one BFS layer." That one sentence is what interviewers are listening for, because it shows you can step outside the tree structure when the question isn't really about the tree.
Mention that BFS processes the queue level by level (record the queue length at the start of each round) and that you stop after k rounds rather than exploring the whole tree.
Follow-up questions
Can you avoid the extra parent map?
Yes, with the ancestor-climbing approach: a DFS returns the distance from each node to the target (or -1 if the target isn't below it). When a node is at distance d from the target, it collects nodes at depth k - d - 1 from its other child. This uses only O(h) stack space.
What if you had to answer many queries with different targets and k on the same tree?
Build the parent map once and reuse it for every BFS. If queries are very frequent, precompute depths and an LCA structure (binary lifting) so the distance between any two nodes is O(log n).
What if values weren't unique and you were given the node itself?
Nothing in the algorithm depends on values; key the parent map and visited set on node identity instead of value. That is the more common form when the target is passed as a reference.
Companies that ask All Nodes Distance K in Binary Tree
All Nodes Distance K in Binary Tree is tagged by 116 companies in our interview dataset. The score shows how often it comes up at each company.
- Viasat100%
- Integral Ad Science100%
- Infinera100%
- Rocket Mortgage96%
- Everbridge95%
- Ticketmaster93%
- Pinwheel92%
- Naver91%
- 6sense91%
- Okta89.2%
- Outreach88%
- Wixcom87.3%
- Scout2487%
- Credit Karma85%
- Liberty It83%
- Derivco83%
- Iodine Software82%
- Elevance Health80%
- Twist Bioscience80%
- Thermo Fisher Scientific79%
- Ansys79%
- Cox Automotive79%
- N2675%
- Mitre75%
and 92 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required