All Nodes Distance K in Binary Tree

Table of Contents +

A tree only points downward. Each node knows its children, not its parent. But this question asks for nodes K steps away from a target, and some of those nodes sit above the target. So you must travel up the tree too. The clever move is to let yourself move in every direction. Once you can do that, a simple spreading search finds the answer.

🎯 The Problem

You get a binary tree, one target node, and a number K. Return every node that is exactly K steps from the target.

The rules:

A binary tree is a structure where each node has up to two children.
Distance means the number of edges on the shortest path between two nodes. An edge is the line between two nodes.
Distance K means K steps away.
Answers can sit below the target, beside it, or above it.
A normal tree walk only goes down. So nodes above the target would be missed.

Let us use a small tree. The root is 3. Its children are 5 and 1. The 5 has children 6 and 2. The target is the node 5, and K is 2.

Input:
  tree:
        3
       / \
      5    1
     / \
    6    2
  target = 5, K = 2

Output: [7, 4, 1]   (order may vary)

Explanation: From node 5, going 2 steps:
  5 -> 3 -> 1 reaches 1.
  5 -> 2 was 1 step; from there no example child here, so we extend below.
We grow the example tree slightly to show all three answers.

To show every kind of answer clearly, let us use this fuller tree. The 2 under 5 has its own children 7 and 4. The 1 has children 0 and 8.

Tree used in the code:
            3
          /   \
         5      1
        / \    / \
       6   2  0   8
          / \
         7   4
  target = 5, K = 2

Output: [7, 4, 1]
Explanation:
  5 -> 2 -> 7  is 2 steps.
  5 -> 2 -> 4  is 2 steps.
  5 -> 3 -> 1  is 2 steps (going UP through the parent 3).

See how 1 is reached by going up to the parent 3 first. That upward move is the whole challenge.

Here is the tree drawn out.

🐢 Approach 1: Search From Every Node (Brute Force)

The idea in one line: measure the distance from the target to every node, and keep the ones that equal K.

The idea:

Pick each node in the tree, one by one.
Run a fresh search from the target to that node.
Find how far it sits from the target.
Keep it if the distance is exactly K.

How it works:

For one node, you walk the tree to measure its distance.
You repeat that for all n nodes.

Why it is weak:

You walk the whole tree once for every node.
The work multiplies. That is about O(n²).
On a big tree this is slow.

Here is the parent-map plus BFS code:

from collections import deque
def distance_k(root, target, k):
    parent = {}
    def build(node, par=None):
        if node:
            parent[node] = par; build(node.left, node); build(node.right, node)
    build(root)
    q, seen = deque([(target, 0)]), {target}
    ans = []
    while q:
        node, dist = q.popleft()
        if dist == k: ans.append(node.val); continue
        for nxt in (node.left, node.right, parent[node]):
            if nxt and nxt not in seen:
                seen.add(nxt); q.append((nxt, dist + 1))
    return ans

⚡ Approach 2: Parent Map Plus Spreading Search (Best)

The idea in one line: add parent links so you can walk in any direction, then spread outward ring by ring from the target.

The idea:

A tree only points down. Each node knows its children, not its parent.
So first record each node’s parent in a hash map.
A hash map holds a key and a value and looks the key up fast.
Now every node has three neighbors: left child, right child, parent.

How it works:

Spread outward from the target, one ring at a time.
This spreading search is breadth-first search, or BFS.
BFS visits all nodes one step away, then two steps away, and so on.
Start at the target at distance zero. Each round, step to every unvisited neighbor.
Keep a visited set so you never count a node twice or walk backward.
When you reach distance K, every node still in the queue is exactly K steps away.

Why it is fast:

One walk sets the parents. One spread visits each node once.
That is O(n) time.

Here is the spread from the target 5, ring by ring, until we reach distance K equal to 2.

Steps to Solve

Walk the tree once and record each node’s parent in a hash map.
Make a queue and put the target node in it. Mark the target as visited.
Track the current distance, starting at zero.
While the distance is less than K, process one full ring at a time.
For each node in the current ring, look at its left child, right child, and parent.
For each neighbor not yet visited, mark it visited and add it to the queue.
After finishing a ring, add one to the distance.
When the distance equals K, every node left in the queue is an answer.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version records parents with one walk, then uses a deque and a set for the breadth-first spread.

from collections import deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def distance_k(root, target, k):
    parent = {}  # node -> its parent

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

    set_parents(root, None)

    queue = deque([target])
    visited = {target}        # never revisit a node
    dist = 0

    while dist < k:                       # stop when we reach distance k
        for _ in range(len(queue)):       # process one full ring
            cur = queue.popleft()
            for nb in (cur.left, cur.right, parent[cur]):  # three neighbors
                if nb and nb not in visited:               # new neighbor
                    visited.add(nb)
                    queue.append(nb)
        dist += 1

    return [node.val for node in queue]   # whatever remains is distance k


root = Node(3)
root.left = Node(5)
root.right = Node(1)
root.left.left = Node(6)
root.left.right = Node(2)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
root.right.left = Node(0)
root.right.right = Node(8)

target = root.left  # node 5
print(distance_k(root, target, 2))

The output of the above code will be:

[7, 4, 1]

Let us walk through the Python version line by line, because the upward move is the part people miss.

The set_parents helper does one walk over the tree. The line parent[node] = par records who the parent is for each node. We pass the current node down as the parent of its children. This is the step that lets us move up later.

The line queue = deque([target]) starts the spreading search at the target. A deque is a double-ended queue that lets us add at the back and remove from the front quickly.

The line visited = {target} is the guard. We mark the target as seen right away. Without this set we would walk back into nodes we already counted, which would loop forever and give wrong distances.

The line while dist < k keeps spreading until we have moved K steps. We stop one ring before going too far.

The line for _ in range(len(queue)) is the trick for processing exactly one ring. We grab the current size of the queue first. Then we only process that many nodes. The neighbors we add during the loop belong to the next ring, so they wait for the next round.

The line for nb in (cur.left, cur.right, parent[cur]) lists all three neighbors of a node. Left child, right child, and the parent. This is where the upward move happens. The parent link lets us reach nodes above the target.

The line if nb and nb not in visited skips empty links and already-seen nodes. For each fresh neighbor we mark it visited and add it to the queue.

After the loop ends, the line return [node.val for node in queue] reads off the answer. Every node still sitting in the queue is exactly K steps from the target.

⏱️ Time and Space Complexity

The slow way searches from every node, so it costs O(n²). The optimal way does one walk to set parents, then one spreading search, and each visits every node once. So it is O(n) time. The space is O(n) for the parent map, the visited set, and the queue.

Approach	Time Complexity	Space Complexity
Search distance from every node	O(n²)	O(n)
Parent map plus breadth-first search	O(n)	O(n)

Tip

The whole trick is turning the tree into a graph you can walk in any direction. Add parent links, then spread out ring by ring. Never forget the visited set, or the search will walk backward and break.

🧩 Key Takeaways

✅ Nodes at distance K can sit below, beside, or above the target.
✅ The tree only points down, so first record each node’s parent to allow moving up.
✅ Treat each node as having three neighbors: left child, right child, and parent.
✅ Spread outward ring by ring with breadth-first search until you reach distance K.
✅ A visited set stops the search from walking backward and counting nodes twice.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Binary Tree Zigzag Level Order Traversal Next Range Sum of BST

All Nodes Distance K in Binary Tree

Follow Us

Follow Us