How do you solve All Nodes Distance K in Binary Tree?

Perform a DFS to assign parent pointers to each node. Then, initiate a BFS from the target node, tracking visited nodes to avoid cycles. After k expansions, the nodes in the queue represent all nodes at distance k. Return their values.

All Nodes Distance K in Binary Tree

Q: What is the time complexity of All Nodes Distance K in Binary Tree?

O(n). Each node is visited once during the DFS to assign parent pointers and once during the BFS traversal, resulting in linear time relative to the number of nodes.

Q: What pattern does All Nodes Distance K in Binary Tree use?

The Pattern: BFS (Shortest Path on Unweighted Graph) The Heuristic: When a problem asks for nodes at a specific distance in a tree or graph, convert the structure into an undirected graph if needed, then use BFS to explore neighbors layer by layer, ensuring the first time nodes are reached corresponds to their shortest distance.

Medium BFS

Problem

Given the root of a binary tree, a target node, and an integer k, return the values of all nodes that are exactly k edges away from the target node.

The number of nodes in the tree is in the range [1, 500].
0 ≤ Node.val ≤ 500
All the values Node.val are unique.
target is a node in the tree.
0 ≤ k ≤ 1000

Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

Output: [7,4,1]

The algorithm first annotates each node with a reference to its parent, effectively converting the tree into an undirected graph. Starting from the target node (5), it performs a breadth-first search (BFS) to explore nodes at increasing distances. At distance 1, neighbors are nodes 6, 2, and 3 (parent). At distance 2, neighbors are nodes 7, 4, and 1. These nodes are collected and returned as the result.

Approach

Straightforward Solution

A naive approach would be to perform a DFS from the target node, but without parent pointers, upward traversal is impossible. Alternatively, one could attempt to find paths by repeated traversals, but this is inefficient and complex.

Core Observation

The problem reduces to finding all nodes at distance k in an undirected graph where edges connect parent and child nodes. The tree structure is inherently directed (parent to children), so adding parent pointers creates bidirectional edges, enabling BFS traversal in all directions.

Path to Optimal

Preview

The key insight is to augment each node with a parent pointer, transforming the tree into an undirected graph. This allows BFS starting from the target node to explore all neighbors (left child, right child, and parent) layer by layer…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Perform a DFS to assign parent pointers to each node. Then, initiate a BFS from the target node, tracking visited nodes to avoid cycles…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited once during the DFS to assign parent pointers and once during the BFS traversal, resulting in linear time relative to the number of nodes.

Space

O(n)

The parent pointers augment the tree with O(n) additional references, and the BFS queue and visited set each require O(n) space in the worst case.

Pattern Spotlight

BFS (Shortest Path on Unweighted Graph)

When a problem asks for nodes at a specific distance in a tree or graph, convert the structure into an undirected graph if needed, then use BFS to explore neighbors layer by layer, ensuring the first time nodes are reached corresponds to their shortest distance.

Solution

Python

1from collections import deque
2
3class Solution:
  def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
      def dfs(node, parent):
          if not node:
              return
          
          node.parent = parent
          dfs(node.left, node)
          dfs(node.right, node)
          
      dfs(root, None)
      queue = deque([target])
      seen = {target}
      distance = 0
      
      while queue and distance < k:
          current_length = len(queue)
          for _ in range(current_length):
              node = queue.popleft()
              for neighbor in [node.left, node.right, node.parent]:
                  if neighbor and neighbor not in seen:
                      seen.add(neighbor)
                      queue.append(neighbor)
          
          distance += 1
      
      return [node.val for node in queue]

Step-by-Step Solution

Annotate Each Node with Its Parent to Enable Bidirectional Traversal

5def dfs(node, parent):
  if not node:
      return
  node.parent = parent
  dfs(node.left, node)
  dfs(node.right, node)
13dfs(root, None)

Objective

To traverse the tree and assign a parent pointer to each node, enabling upward traversal during BFS.

Key Insight

The tree is naturally directed from parent to children, which prevents moving upward during traversal. By performing a DFS that passes the parent node as a parameter and assigning it to each child's 'parent' attribute, the tree is effectively converted into an undirected graph. This transformation is crucial for BFS to explore all neighbors (left, right, and parent) without missing any nodes.

Interview Quick-Check

Core Logic

Assigning parent pointers during DFS creates bidirectional edges, allowing BFS to traverse both downwards and upwards from the target node.

State & Boundaries

The DFS terminates when a null node is reached, ensuring no invalid parent assignments.

Common Pitfalls & Bugs

Forgetting to assign parent pointers or incorrectly passing the parent node can cause incomplete graph construction and incorrect BFS results.

Perform BFS from Target to Collect Nodes at Distance K

To explore the graph layer by layer starting from the target node, collecting all nodes exactly k edges away.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 5 Critical

def dfs(node, parent):

Define a DFS helper function to assign parent pointers to each node.

This function is the foundation for converting the tree into an undirected graph by linking each node to its parent, enabling upward traversal.

Line 6 Critical

if not node:

Check if the current node is null to terminate recursion.

This base case prevents null pointer exceptions and stops the DFS from traversing beyond leaf nodes.

Line 24 Critical

seen.add(neighbor)

Mark the neighbor as visited.

Adding to the visited set immediately upon enqueueing prevents duplicate entries and cycles.

Full line-by-line criticality + rationale for all 20 lines available on Pro.

Test Your Understanding

Why is BFS the appropriate traversal method for finding all nodes at distance k in this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct All Nodes Distance K in Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the All Nodes Distance K in Binary Tree drill

or drill a free problem

1	`from collections import deque`
2
3	`class Solution:`
4	`def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:`
5	`def dfs(node, parent):`
6	`if not node:`
7	`return`
8
9	`node.parent = parent`
10	`dfs(node.left, node)`
11	`dfs(node.right, node)`
12
13	`dfs(root, None)`
14	`queue = deque([target])`
15	`seen = {target}`
16	`distance = 0`
17
18	`while queue and distance < k:`
19	`current_length = len(queue)`
20	`for _ in range(current_length):`
21	`node = queue.popleft()`
22	`for neighbor in [node.left, node.right, node.parent]:`
23	`if neighbor and neighbor not in seen:`
24	`seen.add(neighbor)`
25	`queue.append(neighbor)`
26
27	`distance += 1`
28
29	`return [node.val for node in queue]`

5	`def dfs(node, parent):`
6	`if not node:`
7	`return`
9	`node.parent = parent`
10	`dfs(node.left, node)`
11	`dfs(node.right, node)`
13	`dfs(root, None)`