Pattern visualizer

All Nodes at Distance K in Binary Tree

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. 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]..

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

time O(n)space O(n)step 1 / 12

line 1

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap