All Nodes Distance K in Binary Tree Solution

Problem

Given a binary tree, a target node within it, and an integer k, return all nodes whose distance from the target is exactly k edges — where distance counts both downward edges (to children) and upward edges (to parents).

Example:

[3,5,1,6,2,0,8,null,null,7,4]

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7, 4, 1]
Explanation: Node 7 and node 4 are 2 hops down from 5 (via node 2), and node 1 is 2 hops away by going up to 3 then down to 1.

Intuition

A binary tree only gives you downward pointers, but this problem requires moving upward too. If you could treat the tree as an undirected graph — where every node has up to three neighbors (left child, right child, parent) — then a BFS from the target node naturally finds all nodes at distance k by stopping after exactly k levels. The trick is recording each node's parent in a single DFS pass before BFS begins.

Solution — Parent Map + BFS

Do a single DFS to build a map from every node to its parent. Then run a standard BFS from the target, treating each node's left child, right child, and parent as its three possible neighbors. Stop the BFS when depth reaches k and collect whatever nodes are in the queue.

Steps:

DFS the entire tree, recording parent_map[node] = parent for every node (root's parent is None/null).
Initialize a BFS queue with just the target node and a visited set containing the target.
While the queue is non-empty, check if current depth equals k — if so, return all values currently in the queue.
Otherwise, process every node at the current depth: for each of its three neighbors (left, right, parent), add it to the queue if it exists and hasn't been visited.
Increment depth and repeat.
Return an empty list if BFS exhausts the tree without reaching depth k.

1from collections import deque
2
3def distanceK(root, target, k):
4    parent_map = {}
5
6    def build_parents(node, parent):
7        if not node:
8            return
9        parent_map[node] = parent  # root's parent will be None
10        build_parents(node.left, node)
11        build_parents(node.right, node)
12
13    build_parents(root, None)
14
15    queue = deque([target])
16    visited = {target}
17    distance = 0
18
19    while queue:
20        if distance == k:
21            return [node.val for node in queue]
22        distance += 1
23        for _ in range(len(queue)):  # snapshot size before enqueueing children
24            node = queue.popleft()
25            for neighbor in [node.left, node.right, parent_map[node]]:
26                if neighbor and neighbor not in visited:
27                    visited.add(neighbor)
28                    queue.append(neighbor)
29
30    return []

Time: O(n) — the DFS visits every node once to build the parent map, and BFS visits each node at most once.
Space: O(n) — the parent map stores one entry per node; the visited set and BFS queue together hold at most O(n) nodes.

Complexity Summary

Approach	Time	Space	When to use
Parent map + BFS	O(n)	O(n)	Whenever you need k-distance nodes in any direction on a tree

Common Mistakes

Skipping the visited set — the tree treated as an undirected graph has cycles (you can go down to a child, then back up through its parent). Without tracking visited nodes the BFS loops forever between parent and child.
Forgetting k = 0 — when k is 0 the answer is just the target itself. The code handles this correctly by checking distance == k before any BFS expansion, so the target's value is returned immediately from the initial queue.
Using node values instead of node references as visited keys — duplicate values are allowed in binary trees. Two different nodes can share the same integer value, so a visited set of integers would incorrectly skip the second node. Always key on the node object (reference/pointer), not .val.
Querying parentMap before the DFS completes — the BFS must not start until the full parent map is built. Running DFS and BFS simultaneously would yield incorrect parent links for nodes not yet visited.
Off-by-one on depth tracking — some implementations increment distance after the level loop instead of before, causing an extra level to be processed. Snapshot len(queue) at the start of each level, process exactly that many nodes, then increment once — no more, no less.

All Nodes Distance K in Binary Tree — Solution

Problem

Intuition

Solution — Parent Map + BFS

Complexity Summary

Common Mistakes

Related Problems

Ready to practice? Try it on SkillFlow