All Nodes Distance K in Binary Tree

You are given the root of a binary tree in which every node has a distinct value, a node target that belongs to the tree, and an integer k.

Return the values of all nodes that are exactly k edges away from target. Paths may go up through parents as well as down through children. The values may be returned in any order; return an empty list if there are none.

The tree is written as a level-order array where null marks a missing child, e.g. [1,2,3,null,4]. In the tests target is shown as its value, but your function receives the actual node object.

Example 1

Example 2

Example 3

Constraints

• 1 <= number of nodes <= 500
• 0 <= Node.val <= 500
• All node values are distinct.
• target is a node in the tree.
• 0 <= k <= 1000

Pattern Path · Trees: BFS · problem 96 of 169

Start simple

For every node, compute its distance to target by finding their lowest common ancestor: O(n) per node, O(n²) in total.

The key idea

Distance in a tree means number of edges, and an edge can be walked in either direction. The tree structure only gives you downward links, so the plan is to add the missing upward links and then treat the tree as an ordinary undirected graph.

Step 1, parent map. Traverse the tree once from the root and store parent[child] = node for every child. Now each node has up to three neighbours: left child, right child and parent.

Step 2, BFS from target. Breadth-first search expands in rings: after one level you have every node at distance 1, after two levels every node at distance 2, and so on. Keep a visited set so the search never walks back over an edge it just used (for example child → parent → same child). After exactly k levels, the current frontier is precisely the set of nodes at distance k. If the frontier empties earlier, k is larger than any distance in the tree and the answer is empty.

Because a tree has no cycles, there is a single path between any two nodes, so the BFS level of a node equals its true distance. Each node is visited at most once in each step, giving O(n) time and space.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def distanceK(self, root, target, k):
        # 1. Record each node's parent so we can also walk upward.
        parent = {root: None}
        stack = [root]
        while stack:
            node = stack.pop()
            for child in (node.left, node.right):
                if child:
                    parent[child] = node
                    stack.append(child)

        # 2. BFS outward from target, one ring (distance) per round.
        frontier = [target]
        seen = {target}
        for _ in range(k):
            next_frontier = []
            for node in frontier:
                for neighbour in (node.left, node.right, parent[node]):
                    if neighbour and neighbour not in seen:
                        seen.add(neighbour)
                        next_frontier.append(neighbour)
            frontier = next_frontier
            if not frontier:          # k is larger than any distance in the tree
                break

        return [node.val for node in frontier]

JavaScript

var distanceK = function(root, target, k) {
  // 1. Record each node's parent so we can also walk upward.
  const parent = new Map([[root, null]]);
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    for (const child of [node.left, node.right]) {
      if (child) {
        parent.set(child, node);
        stack.push(child);
      }
    }
  }

  // 2. BFS outward from target, one ring (distance) per round.
  let frontier = [target];
  const seen = new Set([target]);
  for (let d = 0; d < k && frontier.length; d++) {
    const nextFrontier = [];
    for (const node of frontier) {
      for (const neighbour of [node.left, node.right, parent.get(node)]) {
        if (neighbour && !seen.has(neighbour)) {
          seen.add(neighbour);
          nextFrontier.push(neighbour);
        }
      }
    }
    frontier = nextFrontier;
  }

  return frontier.map(node => node.val);
};

What the interviewer is checking

The interviewer wants to see you reframe a tree problem as a graph problem when the needed moves (going up) are not supported by the structure, and then apply BFS cleanly.

Mistakes to avoid

• Only searching the target's subtree and missing nodes reached through the parent.
• Forgetting the visited set, so BFS bounces between a node and its parent and reports wrong nodes.
• Returning [target] incorrectly when k > 0, or not handling k = 0 (the answer is the target itself).
• Comparing nodes by value across different trees; use the given node object (or its unique value) consistently.

Follow-ups to expect

• Can you avoid the parent map? (DFS returning distance to target.)
• What if many queries use the same tree? (Precompute parents once.)
• How would you return nodes within distance k? (Collect every BFS level.)

In real software

Finding everything within a fixed number of hops of a node is how "people you may know" suggestions, file-system proximity searches and network blast-radius analysis work, usually after turning a hierarchy into an undirected graph.

Practice next