All Nodes Distance K in Binary Tree — LC 863 BFS with Parent Map

Problem Statement#

LeetCode 863 — All Nodes Distance K in Binary Tree | Difficulty: Medium

Given the root of a binary tree, a target node, and an integer k, return an array of the values of all nodes that have a distance k from the target node. The answer can be returned in any order.

Constraints:

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

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

Input:  root = [1], target = 1, k = 3
Output: []

Why This Problem Matters#

All Nodes Distance K is a popular FAANG interview question because it tests a key insight: a tree is just a graph with directed edges, and standard BFS gives shortest distances in unweighted graphs. Amazon and Google ask it to see whether candidates can bridge the gap between tree problems (which feel special) and graph problems (which have a well-known toolkit).

The parent pointer technique appears in many follow-ups: LC 1257 (Smallest Common Region), any problem asking you to traverse upward in a tree, and tree serialization problems where you need bidirectional access. Recognizing when to "un-tree" a tree into a graph is a recurring interview skill.

The Core Insight#

Trees only have downward edges (parent to child). To find nodes at distance K, you need to travel both downward and upward. The solution: build a parent map during a DFS, then treat the tree as an undirected graph and run BFS from the target.

BFS from the target processes nodes in order of increasing distance. When BFS has processed all nodes at distance K, the current BFS frontier contains exactly the answer.

Two steps:

1. DFS to build parent[node] = node's parent for every node.
2. BFS from target, using node.left, node.right, and parent[node] as the three possible neighbors.

Visual Dry Run#

Tree: [3, 5, 1, 6, 2, 0, 8], target = 5, k = 2

Parent map after DFS: {3: None, 5: 3, 1: 3, 6: 5, 2: 5, 0: 1, 8: 1}

BFS from target node 5:

At dist = 2: queue = nodes 7, 4, 1 → return [7, 4, 1].

Solution (Optimal)#

from collections import deque
 
class Solution:
    def distanceK(self, root, target, k: int):
        # Step 1: build parent map via DFS
        parent = {}
        def build_parent(node, par):
            if not node:
                return
            parent[node] = par
            build_parent(node.left, node)
            build_parent(node.right, node)
 
        build_parent(root, None)
 
        # Step 2: BFS from target treating tree as undirected graph
        visited = {target}
        queue = deque([target])
        dist = 0
 
        while queue:
            if dist == k:
                return [node.val for node in queue]
 
            for _ in range(len(queue)):
                node = queue.popleft()
                for neighbor in [node.left, node.right, parent.get(node)]:
                    if neighbor and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
 
            dist += 1
 
        return []

var distanceK = function(root, target, k) {
    // Step 1: build parent map
    const parent = new Map();
    function buildParent(node, par) {
        if (!node) return;
        parent.set(node, par);
        buildParent(node.left, node);
        buildParent(node.right, node);
    }
    buildParent(root, null);
 
    // Step 2: BFS from target
    const visited = new Set([target]);
    let queue = [target];
    let dist = 0;
 
    while (queue.length) {
        if (dist === k) return queue.map(n => n.val);
 
        const next = [];
        for (const node of queue) {
            for (const nb of [node.left, node.right, parent.get(node)]) {
                if (nb && !visited.has(nb)) {
                    visited.add(nb);
                    next.push(nb);
                }
            }
        }
        queue = next;
        dist++;
    }
 
    return [];
};

Time: O(n) — DFS visits all nodes once, BFS visits all nodes at most once Space: O(n) — parent map, visited set, and queue each hold at most n entries

Common Mistakes#

• Trying to traverse upward without a parent map — trees only have downward pointers natively
• Not using a visited set — BFS will cycle back to the parent of each node infinitely
• Returning when dist == k before processing the queue for that distance level — check at the start of the loop, not at the end
• Using node identity (value) in the visited set instead of node object — values are unique here, but using the object is cleaner

Interview Tips#

• State the two-phase approach (DFS to build parent map, BFS to find distance-K nodes) before coding
• Draw the undirected graph version of the tree to help the interviewer follow your reasoning
• Note that BFS guarantees shortest distances in unweighted graphs — this is why it gives exact distance K nodes
• Mention that the parent map approach works for any tree, not just binary trees

Follow-up Questions#

• What if you need to find nodes at distance exactly K from any node in a set of targets? Use multi-source BFS: seed the queue with all targets at distance 0.
• What if the tree is weighted (edge weights)? Replace BFS with Dijkstra's algorithm using a min-heap.
• Can you solve this without a parent map using pure DFS? Yes — DFS from root can track the path to target and "fan out" from there, but the code is more complex.
• What is the space complexity if the tree is perfectly balanced vs skewed? DFS recursion stack is O(log n) balanced vs O(n) skewed; the parent map is always O(n).

Key Takeaways#

• Trees are directed graphs; to traverse upward, build a parent map first
• BFS from the target on the undirected graph gives all nodes at exactly distance K
• Three neighbors per node: left child, right child, and parent
• A visited set is mandatory to prevent BFS from revisiting ancestors
• Time and space are both O(n) — this is optimal since you must inspect all nodes in the worst case
• The DFS-to-build-parent + BFS-for-distance pattern appears in many tree-as-graph problems
• Returning at dist == k (before processing the frontier) is the clean termination condition