863. All Nodes Distance K In Binary Tree

Finding specific nodes in a binary tree based on their distance from a target node is a classic algorithmic challenge that tests a developer’s understanding of tree traversal, recursion, and graph theory concepts. The answer can be returned in any order. LeetCode 863, All Nodes Distance K in Binary Tree, presents exactly this scenario: given the root of a binary tree, a target node, and an integer k, return a list of the values of all nodes that have a distance k from the target node. This problem is a favorite in technical interviews because it elegantly bridges the gap between hierarchical tree structures and undirected graph traversal.

Understanding the Core Challenge

At first glance, the problem seems straightforward. If the target node is the root, a simple Depth-First Search (DFS) or Breadth-First Search (BFS) tracking depth will yield the answer. Even so, the complexity arises because the target node can be anywhere in the tree. In a standard binary tree, nodes only have pointers to their children (left and right). They lack a pointer to their parent It's one of those things that adds up. But it adds up..

To find nodes at distance k, we must move in three directions:

1. Downward to the left child.
2. In real terms, Downward to the right child. 3. Upward to the parent.

Since the native tree structure only supports downward movement, we must augment the structure or change our perspective to enable upward traversal. This realization is the key to unlocking the most efficient solutions.

Approach 1: Convert Tree to Undirected Graph

The most intuitive approach for developers comfortable with graph algorithms is to treat the binary tree as an undirected graph. In this model, every node is a vertex, and edges exist between a node and its left child, right child, and parent.

It sounds simple, but the gap is usually here.

Algorithm Steps

1. Build the Adjacency List: Traverse the tree (using DFS or BFS) starting from the root. For every node, create edges connecting it to its left and right children. Since the graph is undirected, ensure the children also link back to the parent. A HashMap<TreeNode, List<TreeNode>> or Map<Integer, List<Integer>> works perfectly for this.
2. BFS from Target: Initialize a queue with the target node and a visited set to prevent cycles. Perform a standard level-order BFS.
3. Track Distance: Process nodes level by level. Decrement k after finishing each level. When k reaches 0, the nodes currently in the queue are exactly at distance k from the target.
4. Collect Results: Extract the values from the queue and return them.

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes. We visit every node once to build the graph and potentially once more during BFS.
• Space Complexity: O(N). The adjacency list stores 2*(N-1) edges, the queue holds up to O(N) nodes, and the visited set holds O(N) nodes.

This approach is strong and easy to implement if you have a graph template ready. It transforms an unfamiliar tree problem into a familiar shortest-path-in-unweighted-graph problem Took long enough..

Approach 2: Recursive DFS with Parent Pointers (No Explicit Graph)

We can optimize space slightly and avoid building an explicit adjacency list by annotating the tree nodes with parent pointers during a preliminary traversal.

Algorithm Steps

1. Annotate Parents: Run a DFS from the root. Pass the parent node as an argument. Assign node.parent = parent for every node visited.
2. BFS/DFS from Target: Start from the target node. Explore three neighbors: node.left, node.right, and node.parent.
3. Visited Set: Maintain a visited set (using node references or values) to avoid going back and forth between parent and child.
4. Stop at Distance K: When the current distance equals k, add the node value to the result list and stop exploring deeper from that branch.

Why This Works Well

This method keeps the logic contained within the tree node structure (conceptually). It avoids the overhead of a HashMap for the adjacency list, though the asymptotic space complexity remains O(N) due to the recursion stack (for annotation) and the BFS queue/visited set.

Approach 3: The Elegant Single-Pass Recursive Solution

This is often the "optimal" solution expected in senior-level interviews. It solves the problem in one single post-order traversal without extra data structures for parent pointers or graphs (aside from the recursion stack and the output list). It relies on the return value of the recursive function to signal the distance from the current node to the target.

The Core Logic

The recursive function dfs(node) returns the distance from node to the target That alone is useful..

• If node == target: Return 0.
• If node is null: Return -1 (signaling target not in this subtree).
• Recurse left (L) and right (R).

There are three distinct cases to handle at every node:

Case A: Target found in Left Subtree (L != -1) The target is L edges below the left child.

• The current node is at distance L + 1 from the target.
• If L + 1 == k, the current node is an answer.
• We must also find nodes in the right subtree that are at distance k - (L + 1) - 1 = k - L - 2 from the right child. We call a helper subtree_add(node.right, k - L - 2).
• Return L + 1 to the parent.

Case B: Target found in Right Subtree (R != -1) Symmetric to Case A That's the part that actually makes a difference..

• Current node distance is R + 1.
• If R + 1 == k, add current node.
• Call subtree_add(node.left, k - R - 2).
• Return R + 1.

Case C: Target not in either subtree (L == -1 && R == -1) Return -1.

The Helper Function: subtree_add(node, dist)

This standard helper adds all nodes at depth dist below the given node to the result list.

• If node is null or dist < 0: Return.
• If dist == 0: Add node.val to result; Return.
• Recurse subtree_add(node.left, dist - 1) and subtree_add(node.right, dist - 1).

Why This Is Brilliant

It handles the "upward" movement implicitly. When the recursion unwinds back up the call stack from the target toward the root, the return value carries the distance information. The parent nodes use this distance to calculate if they are the answer or if they need to look "across" into the other subtree Simple as that..

Complexity Analysis

• Time Complexity: O(N). Every node is visited a constant number of times (once in main DFS, potentially once in subtree_add).
• Space Complexity: O(H) where H is the height of the tree (recursion stack). In the worst case (skewed tree), O(N). This is better than the O(N) explicit space of the graph/parent-pointer approaches.

Detailed Walkthrough with an Example

Consider the tree: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2.

Visual structure: