All Nodes Distance K in Binary Tree - Solution & Explanation

Problem Overview: Given the root of a binary tree, a target node, and an integer k, return all node values that are exactly k edges away from the target. The challenge is that nodes at distance k may lie in the target’s subtree, its ancestors, or in sibling subtrees higher in the tree.

Approach 1: Breadth-First Search using Parent Map (O(n) time, O(n) space)

A binary tree normally allows traversal only downward. To move both up and down, first build a parent map that records each node’s parent using a traversal of the tree. After that, run a BFS starting from the target node. During BFS, treat the tree like an undirected graph where neighbors are left, right, and parent. Maintain a visited set to avoid revisiting nodes. Stop the BFS when the current distance equals k and collect all nodes in that level.

This approach works because BFS explores nodes level by level, so the first time you reach distance k you already have the correct nodes. The preprocessing step ensures upward traversal is possible. Time complexity is O(n) for building the parent map and running BFS. Space complexity is O(n) for the parent map, queue, and visited set. This method relies heavily on Breadth-First Search and tree traversal concepts from Binary Tree problems.

Approach 2: Depth-First Search with Backtracking (O(n) time, O(h) space)

This method avoids building an explicit parent map. Instead, run a DFS to locate the target node and track the distance while backtracking through the recursion stack. When the DFS reaches the target, collect nodes at distance k in its subtree. While returning from recursion, compute how far each ancestor is from the target. If an ancestor is d edges away, search the opposite subtree for nodes at distance k - d - 1.

The key insight is that backtracking naturally provides ancestor distances without extra data structures. Each recursive call either finds the target or returns the distance from the current node to the target. When the target lies in one subtree, the algorithm explores the other subtree to locate nodes at the remaining distance. This approach runs in O(n) time because every node is visited at most once, and uses O(h) recursion space where h is the tree height. It combines tree recursion with techniques from Depth-First Search.

Recommended for interviews: The BFS + parent map approach is the most commonly expected solution. It’s straightforward and clearly models the problem as graph traversal from the target node. Implementing the DFS backtracking solution demonstrates deeper understanding of tree recursion and distance propagation. Showing the BFS version first proves correctness quickly, while the DFS version highlights strong problem-solving skills.