DSA Tracker

Visualize

All Nodes Distance K in Binary Tree

Turn the tree into a graph with a parent map, then BFS outward in rings

time O(n)space O(n)

Distance in a tree radiates three ways from any node: into its left child, its right child, and up to its parent. Plain tree nodes have no parent pointer, so a normal downward traversal can never look back up. Fix that first with a parent map, then the problem becomes plain BFS: expand outward one ring of edges at a time until dist reaches k, and whatever is left in the queue is the answer.

Details

Animated on: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2 — return every node exactly k edges from target. Expected: [7, 4, 1].

Problem:All Nodes Distance K in Binary TreeMedium

Turn the tree into a graph with a parent map, then BFS outward in rings

step 1 / 12

6
5
7
2
4
3
0
1
8

Target is node 5. We want every node exactly k=2 edges away — up through parents as well as down through children.

Pseudocode
1FUNCTION distanceK(root, target, k):
2  parent <- MAP() built by DFS FROM root
3  queue <- [target]
4  visited <- {target}
5  dist <- 0
6  WHILE queue NOT EMPTY AND dist < k:
7    nextQueue <- []
8    FOR EACH node IN queue:
9      FOR EACH neighbor IN {node.left, node.right, parent[node]}:
10        IF neighbor != null AND neighbor NOT IN visited:
11          ADD neighbor TO visited AND APPEND TO nextQueue
12    queue <- nextQueue
13    dist <- dist + 1
14  RETURN values of nodes IN queue

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Target is node 5. We want every node exactly k=2 edges away — up through parents as well as down through children.
  2. Standard tree nodes only point downward, so first walk the whole tree from the root and record each node's parent — that turns the tree into an undirected graph we can search in any direction.
  3. Parent map built in O(n). Each badge is that node's parent value (the root has none).
  4. Start the radial search at the target itself: queue = [5], dist = 0.
  5. dist (0) is not yet k (2), so expand every node currently in the queue.
  6. dist becomes 1. Still short of k, so we expand again next round.
  7. dist (1) is not yet k (2), so expand every node currently in the queue.
  8. Node 6: look at its left child, right child and parent. nothing new, its neighbors are already visited.
  9. Node 2: look at its left child, right child and parent. add 7 and 4.
  10. Node 3: look at its left child, right child and parent. add 1.
  11. dist becomes 2. That equals k, so the loop stops here.
  12. Return the queue's values: [7, 4, 1] — every one of these is exactly k=2 edges from 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve All Nodes Distance K in Binary Tree in the editorAll Binary Trees problemsBack to roadmap