All Nodes Distance K in Binary Tree: Parent Pointers and BFS

Given the root of a binary tree, a target node, and an integer K, return a list of all nodes that are distance K from the target. Distance means the number of edges on the path between two nodes.

This is LeetCode 863: All Nodes Distance K in Binary Tree, and it sits at the intersection of trees and graphs. The tree structure only gives you downward pointers (left child, right child), but the answer might require going upward through a parent. That tension is what makes this problem interesting.

Why this problem matters

Most tree problems only ask you to move downward. Maximum depth, path sum, invert binary tree, level order traversal: they all flow from root toward leaves. This problem breaks that pattern because the target node is not the root, and some result nodes might be ancestors of the target or in completely different subtrees.

That forces you to think about the tree differently. A binary tree is really just an undirected graph where each node connects to at most three neighbors: its left child, its right child, and its parent. The tree structure hides the parent relationship, but you can recover it with a single traversal.

Once you see the tree as a graph, the problem reduces to "find all nodes at distance K from a source node in an undirected graph." That is a textbook BFS problem. The conceptual leap from tree to graph is the real lesson here, and it unlocks a whole family of problems where you need to navigate a tree in all directions.

The brute force approach

def distance_k_brute(root, target, k):
    result = []

    def distance_from(node, target):
        if not node:
            return -1
        if node == target:
            return 0
        left = distance_from(node.left, target)
        if left >= 0:
            return left + 1
        right = distance_from(node.right, target)
        if right >= 0:
            return right + 1
        return -1

    def collect_at_depth(node, depth, k):
        if not node:
            return
        if depth == k:
            result.append(node.val)
            return
        collect_at_depth(node.left, depth + 1, k)
        collect_at_depth(node.right, depth + 1, k)

    def solve(node, target, k):
        if not node:
            return
        dist = distance_from(node, target)
        if dist == k:
            result.append(node.val)
        if dist >= 0 and k - dist >= 0:
            if node.left:
                left_dist = distance_from(node.left, target)
                if left_dist >= 0:
                    solve(node.left, target, k)
                else:
                    collect_at_depth(node.left, dist + 1, k)
            if node.right:
                right_dist = distance_from(node.right, target)
                if right_dist >= 0:
                    solve(node.right, target, k)
                else:
                    collect_at_depth(node.right, dist + 1, k)

    solve(root, target, k)
    return result

This works but is messy. You are computing distances repeatedly from various nodes, and the logic for deciding which subtree to search gets tangled. The code is hard to read, hard to debug, and the repeated distance_from calls push the time complexity toward O(n^2) in the worst case.

The key insight: treat the tree as an undirected graph

A binary tree gives you .left and .right pointers, which let you move downward. But there is no .parent pointer to move upward. The trick is to build one yourself.

Run a DFS (or BFS) over the entire tree. For each node, record its parent in a hash map: parent[node] = node's parent. Now every node has three potential neighbors: node.left, node.right, and parent[node]. The tree is effectively an undirected graph.

With this graph in hand, you run BFS from the target node, expanding level by level. Each BFS level corresponds to one unit of distance. When you have expanded K levels, every node in the queue is exactly K edges from the target. Collect them and return.

Walking through it step by step

Notice the two-phase structure. Phase one builds the parent map with a simple DFS. Phase two is pure BFS from the target, treating left, right, and parent as equal neighbors. The visited set prevents the BFS from doubling back.

The optimal solution

from collections import deque

def distance_k(root, target, k):
    parent = {}

    def dfs(node, par):
        if not node:
            return
        parent[node] = par
        dfs(node.left, node)
        dfs(node.right, node)

    dfs(root, None)

    queue = deque([target])
    visited = {target}
    distance = 0

    while queue:
        if distance == k:
            return [node.val for node in queue]
        distance += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            for neighbor in (node.left, node.right, parent[node]):
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

    return []

Complexity analysis

Time is O(n) because the DFS to build parent pointers visits every node once, and the BFS also visits every node at most once. Both passes are linear.

Space is O(n) for three reasons: the parent hash map stores one entry per node, the visited set can grow to hold every node, and the BFS queue can hold up to O(n) nodes in the worst case. The DFS call stack adds O(h) where h is the height of the tree, but that is dominated by the O(n) from the other structures.

Building blocks

1. Parent pointers (tree-to-graph conversion)

The parent pointer technique converts a tree into an undirected graph. You traverse the tree once, storing each node's parent in a map. After that, any node has up to three neighbors: left child, right child, and parent. This is the standard way to "unlock upward movement" in a tree.

parent = {}
def dfs(node, par):
    if not node:
        return
    parent[node] = par
    dfs(node.left, node)
    dfs(node.right, node)

The same technique applies whenever you need to find paths that go through ancestors, compute distances between arbitrary nodes, or traverse the tree in all directions.

2. BFS level-by-level

Once you have a graph (or a tree with parent pointers), BFS level-by-level finds all nodes at a given distance from a source. The template is:

from collections import deque

queue = deque([source])
visited = {source}
distance = 0
while queue:
    if distance == k:
        return list(queue)
    distance += 1
    for _ in range(len(queue)):
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

The len(queue) snapshot separates one level from the next. This pattern appears in level order traversal, shortest path in unweighted graphs, minimum depth, right side view, and many more problems.

Edge cases

• K = 0: The only node at distance 0 from the target is the target itself. The BFS returns immediately with [target.val].
• Target is the root: The parent pointer for the root is None, so BFS only expands downward. This still works because the None neighbor is filtered out.
• K exceeds the tree depth: The BFS expands level by level until the queue is empty. If you never reach distance K, return an empty list.
• Single-node tree, K = 0: The tree has only one node (which is the target). Return [root.val].
• Target is a leaf: BFS can only go upward (via parent) from a leaf. The algorithm handles this correctly since left and right are None and get filtered out.
• All result nodes are in the same subtree: When target is near the root, all results might be deeper in one subtree. BFS explores all directions equally, so no special handling is needed.

Common mistakes

1. Forgetting to build parent pointers. Without parent pointers, you can only move downward from the target. That misses all result nodes that require going up through an ancestor first.

2. Not using a visited set. In an undirected graph (which the tree becomes after adding parent pointers), BFS without a visited set will loop forever. Node A enqueues parent B, and then parent B enqueues child A again. The visited set prevents this cycle.

3. Mixing up when to collect results. You should check distance == k at the start of the BFS loop, before popping any nodes. The nodes in the queue at that moment are all exactly at distance K. If you check after expanding, you will be off by one.

From understanding to recall

You just worked through the two-phase approach: build parent pointers, then BFS from the target. The logic is clean. Phase one is a standard DFS. Phase two is the same BFS level-by-level template you have seen in level order traversal and shortest path problems. It all fits together.

But this problem tests a conceptual shift, not just code mechanics. The hard part is seeing that you need parent pointers in the first place. In an interview, the pressure is on, and the tree structure tempts you into a pure recursive solution. Without the graph insight, you end up wrestling with awkward recursive distance calculations that are hard to get right.

Spaced repetition helps here because it drills the decision point, not just the code. The first time you review this problem, you recall the parent pointer idea quickly. The second time, you write the BFS from memory. By the third repetition, the entire two-phase pattern is automatic. You see "distance K in a tree" and immediately think "parent map plus BFS," the same way you see "level order" and immediately think "queue with size snapshot."

Related posts

• Binary Tree Level Order Traversal - The core BFS level-by-level template that powers the second phase of this solution
• Lowest Common Ancestor - Another problem where understanding tree structure (parent-child relationships) is key
• Clone Graph - Uses BFS with a hash map to traverse a graph while building a parallel structure, similar to how we use BFS with a visited set here

The parent pointer technique plus BFS level-by-level is a powerful combination. Once you internalize it, any tree problem that involves distances or upward traversal becomes a matter of applying a familiar template.