All Nodes Distance K in Binary Tree
WHAT IT SAYS
Given the root, a target node, and an integer k, return the values of all nodes exactly k edges away from the target.
WHAT IT'S REALLY ASKING
"Distance does not care about direction — a node k steps UP from the target is exactly as far as one k steps down. But your pointers only go down: the tree is a graph with half its edges thrown away. Put the missing edges back, and 'distance k' becomes the most ordinary question in graph theory."
Handle down and up as separate cases
O(n) time if executed perfectly — but the case analysis is the costNodes below the target are easy: DFS down from it, emitting at depth k. For nodes elsewhere, walk from the root, and for each ancestor of the target at distance d, collect nodes at depth k - d in the ancestor's OTHER subtree. Stitch the cases together, being careful not to re-enter the subtree you came from.
WHERE THE WORK IS WASTED — The waste here is not asymptotic; it is structural. One concept — distance — has been split into two mechanisms (descend-from-target, descend-from-ancestors-sideways) that must agree at their seam: the 'do not re-enter the child I came from' bookkeeping is exactly a hand-rolled visited set, and the k - d arithmetic is a hand-rolled BFS depth counter. You are re-implementing, in special cases, the two things a graph traversal gives you as primitives. Every bug in this approach lives at the seam between the two cases — a seam the problem itself never had.
A tree is a graph missing its upward edges.
The asymmetry is entirely an artifact of representation. As a GRAPH, a tree is undirected: each edge connects two nodes, full stop, and 'distance k from a node' is textbook BFS — expand ring by ring, and the k-th ring is the answer. The only reason the problem feels hard is that the TreeNode structure stores each edge in one direction only. Child pointers survive; parent pointers were discarded. So recover them. One O(n) traversal builds a map from each node to its parent — or, equivalently, builds a full adjacency list. That single pass converts the tree into what it always was underneath, and every trace of the case analysis evaporates: up-moves and down-moves become the same move. Then BFS from the target. A visited set replaces the 'don't re-enter where you came from' bookkeeping — and note this is not optional once parent edges exist, because parent-then-child immediately revisits your origin. Expand level by level; when the ring counter hits k, the current frontier IS the answer, verbatim. The deeper point, worth keeping long after this problem: representation is a choice, and the difficulty of a question depends on it. 'Distance k' is awkward on a parent-blind structure and trivial on an adjacency list. When a problem's stated structure makes a symmetric concept asymmetric, the first move is not a cleverer algorithm — it is one cheap pass to build the representation in which the question is native. The O(n) map is not overhead; it is the solution.
Build parent links, then BFS k rings
O(n) time, O(n) space for the parent map, visited set, and queueTraverse once, recording parent[node] for every node. BFS from the target with a visited set, exploring left child, right child, and parent as equal neighbours. Count rings; when the counter reaches k, return the values currently in the queue.
Fix the Representation First
YOU'LL SEE IT AGAIN WHEN
- The question is symmetric (distance, connectivity, nearest) but the given structure stores relations in one direction only.
- The clever direct solution splits one concept into coordinated cases whose seam requires hand-rolled visited/depth bookkeeping.
- One cheap preprocessing pass (parent map, adjacency list, reverse index) would make the question native to a standard traversal.