All Nodes Distance K in Binary Tree
All Nodes Distance K in Binary Tree: given the root, a target node, and an integer k, return the values of every node exactly k edges away from the target.
- The number of nodes is in the range [1, 500]
- 0 <= Node.val <= 500
- All Node.val are unique
- target is the value of one of the nodes in the tree
- 0 <= k <= 1000
Intuition
Distance here is undirected — a node k steps away may sit below the target, above it, or across in a sibling subtree. Tree pointers only lead downward, so the structure must first be made bidirectional by recording each node's parent. Once every node can reach all three neighbours, the tree is an ordinary undirected graph and a breadth-first search from the target stops precisely at depth k.
When a tree question measures undirected distance, or asks about nodes above as well as below, convert it to a graph with a parent map and run BFS. The tell is a distance that can travel upward. Amount of Time for Binary Tree to Be Infected is the same transformation.
Approach
Before reading on: construct a case where the answer lies in a subtree the target is not inside, and note which pointer you would need to get there. Then work out what goes wrong in the BFS without a visited set.
Why downward-only traversal is insufficient
A DFS from the target reaches only its descendants, but the answer routinely includes nodes reached by walking up to an ancestor and then down a different branch. In the standard example the target's answers include a node in the opposite subtree entirely, whose path leaves the target, climbs to the root, and descends the other side. Since TreeNode carries no parent pointer, that upward step is not expressible until one is supplied, which is why the parent map is the enabling step rather than an optimisation.
Building the parent map, then treating the tree as a graph
One preliminary traversal from the root records parent[child] = node for every node. After it, each node has up to three neighbours — left child, right child, and parent — and the structure is an undirected graph with n nodes and n - 1 edges. Nothing about the tree's shape matters from this point on; the problem reduces to all vertices at distance exactly k from a source, which is the textbook use of breadth-first search.
BFS by levels, and the visited set that prevents backtracking
Start a queue holding only the target and expand level by level, counting the levels traversed. When the counter reaches k, every node still in the queue is exactly k edges away, so the whole queue is the answer. A visited set is mandatory: without it the search steps from a node to its parent and immediately back down to the same node, revisiting it at distance 2 and producing both duplicates and wrong distances. Time and space are both O(n) — one map entry and one visit per node.
Solution & live demo
Common pitfalls
Searching only the target's subtree
def dfs(node, d):
if d == k: result.append(node.val)
dfs(node.left, d + 1)
dfs(node.right, d + 1)build a parent map, then BFS in all three directions
Child pointers reach only descendants, so every node above the target or in a sibling subtree is missed. Those nodes are usually the majority of the answer.
Omitting the visited set
for nxt in (node.left, node.right, parent[node]):
queue.append(nxt)if nxt and nxt not in seen:
seen.add(nxt)
queue.append(nxt)The search walks to a parent and straight back to the node it came from, recording it again at distance 2. The result gains duplicates and nodes at the wrong distance, and the queue never drains.
Checking the distance after expanding a level
expand the level, then if distance == k: return ...
if distance == k: return [n.val for n in queue] then expand
Testing after expansion reports the nodes at distance k + 1. The queue holds the current level's nodes before expansion, so the check belongs first — which is also what makes k = 0 return the target itself.
Edge cases
The target itself is the only node at distance 0, returned before any expansion.
The queue empties before the level counter reaches k, so an empty list is returned.
The parent map is unused for it, and the search descends only.
The first step must go upward through the parent link.
BFS reaches them at the same level, which is why the whole queue is returned at once.