DSA sheet · Trees · DFS traversal pattern

All Nodes at Distance K

This problem asks us to walk outwards from one node, in every direction, for exactly K steps. The tricky part is that a binary tree only lets us walk down (parent → child). Walking up is not built in. The teacher's whole lesson is about one idea: if you can't walk up, remember who your parent is. Once every node knows its parent, the problem becomes a simple level-by-level spread from the target. It is a favourite interview question because it mixes DFS (to build the parent map) and BFS (to spread out K steps) in one solution.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Words you must know first
• Part A · Step 1 of the solution: the parent map with DFS
• Part B · Step 2 of the solution: spreading K steps from the target with BFS
• Part C · Revision page

Part 0 · Before starting

Terms used on this page

• Parent: the node directly above a node. In the tree below, the parent of 5 is 3.
• Children: the nodes directly below a node (its left and right). The children of 5 are 6 and 2.
• Distance between two nodes: the number of edges (lines) you walk to go from one to the other, along the tree. You may go down and up. From 5 to 7 is 2 (5 → 2 → 7). From 5 to 1 is also 2 (5 → 3 → 1).
• Target: the node we start from. LeetCode gives it as the node itself (a reference), not just a value.
• Level (in BFS): a group of nodes that are all the same distance from the start. Here "level 1" means "everything 1 step from the target".

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

The example used all through this page

            3
          /   \
         5     1
        / \   / \
       6   2 0   8
          / \
         7   4

  target = 5,  k = 2   →   answer = [7, 4, 1]

Why? From 5, two steps down: 5 → 2 → 7 and 5 → 2 → 4. Two steps up and over: 5 → 3 → 1. Nothing else is exactly 2 steps away (6 is only 1 step, 0 and 8 are 3 steps).

Part A · Step 1: the parent map with DFS

LeetCode 863 · All Nodes Distance K in Binary Tree

1The question in simple words

You get the root of a binary tree, a target node inside it, and a number k. Return the values of all nodes that are exactly k steps away from the target. Steps can go to a child or to the parent. Any order is fine.

So the target is like a stone dropped in water: we want the ring of nodes at exactly k steps, spreading down into its own subtree and also up through its parent and then down the other branches.

2What the constraints tell us

• Number of nodes: 1 to 500 → the tree is never empty, and it's tiny. The teacher's point: with n ≤ 500, even O(n²) would pass easily (500² = 250,000, far below 10⁸). So we don't have to be clever about speed. We just need a correct way to move upwards.
• All values are unique, and the target is a node that really exists in the tree.
• k is between 0 and 1000 → k can be 0 (answer is just the target itself), and k can be bigger than the tree (answer is empty).

3Intuition: the real problem is going up

Going down from 5 is free: node.left and node.right are right there. Going up from 5 to 3 is the problem. A node has no link back to its parent. The arrows in a tree only point downwards.

The teacher says: don't try to flip the tree or change its directions. That's not needed. Instead, do something simpler: walk the tree once, and for every node write down "my parent is ___" in a dictionary. Later, whenever we want to go up from a node, we just look it up and jump to its parent.

Think of it as giving every node a little sticky note with its parent's name. The tree's arrows still point down, but now every node also knows the way up.

4Building the logic from the example

Which data structure stores "node → its parent"?

We want to link one node to one other node: a key and a value. That's exactly what a hash map does. In Python that's a dict: parent[node] = its parent node.

How do we fill it? Pass the parent down

We start at the root. The root has no parent, so we store None for it. Then, when we go to the root's left child and right child, we hand them the root as their parent. They store it, and hand themselves down to their own children. And so on.

• 3 → parent None. Then visit 5 and 1, telling them "your parent is 3".
• 5 → parent 3. Then visit 6 and 2, telling them "your parent is 5".
• 6 → parent 5. 2 → parent 5. Then 7 and 4 get parent 2.
• 1 → parent 3. Then 0 and 8 get parent 1.

The base case

This is a normal DFS, so it needs a stopping point: if the node is None, there's nothing to store. Just return.

5Approach steps

1. Make an empty dictionary parent.
2. Call build(root, None).
3. Inside build(node, par): if node is None, return.
4. Store parent[node] = par.
5. Recurse on the left child with node as its parent, then on the right child with node as its parent.

6Code (Python)

def build_parent(node, par, parent):
    if node is None:              # base case: nothing to store
        return
    parent[node] = par            # sticky note: "my parent is par"
    build_parent(node.left, node, parent)    # I am my left child's parent
    build_parent(node.right, node, parent)   # I am my right child's parent

7Code line by line

8Dry run using the call stack

1. build(3, None): store 3 → None. Go left.
2. build(5, 3): store 5 → 3. Go left.
3. build(6, 5): store 6 → 5. Both children are None, so both calls return at once. 6 is done.
4. Back in 5, go right: build(2, 5): store 2 → 5. Go left.
5. build(7, 2): store 7 → 2. Leaf, done. Then build(4, 2): store 4 → 2. Leaf, done.
6. 2 is done, 5 is done. Back in 3, go right: build(1, 3): store 1 → 3.
7. build(0, 1): store 0 → 1. build(8, 1): store 8 → 1. Everything is done.

9Complexity & remember

• Time O(n): every node is visited once and stored once.
• Space O(n) for the dictionary (one entry per node), plus O(h) for the recursion stack, where h is the height of the tree.

Part B · Step 2: spreading K steps from the target with BFS

1The question, now that we have parents

Every node now has three possible neighbours: its left child, its right child, and its parent (from the map). The question becomes: starting at the target, take one step at a time to any neighbour, and after exactly k steps, which nodes are we on?

2What the constraints tell us here

• k can be 0 → before taking any step, the answer is just [target.val]. Our loop must check "have we reached k?" before moving.
• k can be larger than the tree (up to 1000 while n ≤ 500) → we may run out of nodes before reaching k. Then the answer is an empty list, and the code must not crash.

3Intuition: rings around the target

Picture the target in the middle. First collect everything 1 step away. From those, collect everything 1 more step away (that's 2 steps from the target). Keep going, ring by ring. When we reach ring k, the nodes in it are the answer.

"Collect all neighbours, then all their neighbours, ring by ring" is exactly BFS with levels. Each ring is one level. A queue holds the current ring.

4Building the conditions from the example

Distance 1 from 5

Down: 5.left = 6 and 5.right = 2. Up: parent[5] = 3. So ring 1 = 6, 2, 3. These go in the queue.

Distance 2: take one more step from every node in ring 1

We take the nodes of ring 1 out one by one and look at their children and parent.

• Why must we also look at 6's children, even though 6 has none here? Because if 6 had children (say 0 and 1), they would be 2 steps from 5, and must be in the answer. So every node in the ring gets the same treatment: left, right, parent.
• From 6: no children. Its parent is 5… but wait.

The problem: going back where we came from

If 6 adds its parent 5, then 5 lands in ring 2. That would claim "5 is 2 steps away from 5" (5 → 6 → 5). That's nonsense. We just walked out and walked back in.

With the visited set, ring 2 works out like this:

• 6: left None, right None, parent 5 → already visited. Adds nothing.
• 2: left 7 ✓, right 4 ✓ (new, add both). Parent 5 → visited, skip.
• 3: left 5 → visited, skip. Right 1 ✓ (new, add). Parent None → nothing above the root.

Ring 2 = 7, 4, 1. That's the answer ✓.

The three checks for each neighbour

For the left child, the right child and the parent, the check is the same shape:

1. It must exist (not None). The root's parent is None, leaves have None children.
2. It must not be visited yet.
3. If both pass → mark it visited and push it into the queue.

Why process the queue level by level (using its size)?

We need to know where one ring ends and the next begins, so we can count the distance. At the start of each round, the queue holds exactly one ring. We read len(queue) and pop exactly that many. Everything pushed during the round belongs to the next ring. After the round, distance goes up by 1.

Where exactly do we check "distance == k"?

Only between rings, never in the middle of one. A ring is only complete after its whole round has finished. So the check goes at the top of the while loop, before reading the size. If it matches, we break. The queue then holds exactly the nodes of ring k.

• This also handles k = 0: at the very first check, distance is 0, so we break immediately and the queue holds just the target.
• And k too large: the queue runs empty, the while loop ends on its own, and we return an empty list.

Why not start the BFS from the root?

You might think: "first search the tree from the root until I find the target, then begin". The teacher says that's not needed. LeetCode hands us the target node. From it, we can go down with .left/.right, and up with the parent map. So we can start the BFS directly at the target. The parent map is the only reason we needed the root at all.

The answer at the end

The queue holds nodes, but we must return values. So read .val from each node left in the queue.

5Approach steps (the full solution)

1. Build the parent map with the DFS from Part A.
2. Make a queue with the target in it, and a visited set with the target in it. Set distance = 0.
3. While the queue is not empty: if distance == k, break.
4. Otherwise, read the size of the queue and pop that many nodes. For each popped node, push its left child, right child and parent, but only if they exist and are not visited (mark them visited when pushing).
5. After the round, distance += 1.
6. Return the values of the nodes still in the queue.

6Code (Python)

from collections import deque

class Solution:
    def distanceK(self, root, target, k):
        parent = {}
        self.buildParent(root, None, parent)      # Step 1 (DFS)

        queue = deque([target])                   # Step 2 (BFS) starts at target
        visited = {target}
        distance = 0

        while queue:
            if distance == k:                     # this ring is ring k: stop
                break
            size = len(queue)                     # nodes in the current ring
            for _ in range(size):
                cur = queue.popleft()
                for nxt in (cur.left, cur.right, parent[cur]):
                    if nxt is not None and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
            distance += 1                         # one more step outwards

        return [node.val for node in queue]

    def buildParent(self, node, par, parent):
        if node is None:
            return
        parent[node] = par
        self.buildParent(node.left, node, parent)
        self.buildParent(node.right, node, parent)

The teacher writes three separate if blocks (left, right, parent). The small loop over (cur.left, cur.right, parent[cur]) is the same three checks, written once. The order (left, right, parent) is kept, so the queue looks exactly like her dry run.

7Code line by line

8Dry run: watch the queue

target = 5, k = 2. Yellow = the nodes popped in this round.

The teacher adds a thought: what if k were 3? Then we'd do one more round from 7, 4, 1. 7 and 4 are leaves whose parent 2 is visited, so they add nothing. 1's left 0 and right 8 are new, and its parent 3 is visited. Ring 3 = [0, 8]. In this case we walked over every node before stopping. That's the worst case for time.

9Complexity & remember

• Time O(n). Building the parent map visits every node once: O(n). The BFS can also visit every node once in the worst case (when k is large, like the k = 3 example): another O(n). The teacher stresses it's n + n = 2n, not n × n, because the two parts run one after the other, not one inside the other. 2n is still linear.
• Space O(n). The parent map O(n) + the visited set O(n) + the queue O(n) + the recursion stack O(h). That's about 3n + h, and since h ≤ n, it's O(n).

Part C · Revision page

n7, n4 = TreeNode(7), TreeNode(4)
n2 = TreeNode(2, n7, n4)
n5 = TreeNode(5, TreeNode(6), n2)
root = TreeNode(3, n5, TreeNode(1, TreeNode(0), TreeNode(8)))

s = Solution()
print(sorted(s.distanceK(root, n5, 2)))   # [1, 4, 7]
print(sorted(s.distanceK(root, n5, 3)))   # [0, 8]
print(s.distanceK(root, n5, 0))           # [5]
print(s.distanceK(root, n7, 10))          # []

Based on this video: Print All Nodes at Distance K