Tree as a graph (parent pointers)

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A tree: 3 at the top; 5 and 1 below; 6 and 2 under 5; 0 and 8 under 1; 7 and 4 under 2. Which nodes are exactly 2 steps away from node 5? By eye: 7 and 4 (down through 2), and 1 (up to 3, then down). Notice the third one: it goes up. In a tree drawn on paper you can walk in any direction. In the computer, a node points only to its children; standing on 5, you cannot see 3.

The by-hand fix is to redraw the tree so that 5 is at the top. Then "2 steps away" is just "two levels down". Redrawing is the right idea, and the pattern below does it without actually redrawing anything.

Build the structure, one piece at a time

Piece one: a parent map. Walk the whole tree once from the root; every time you step from a node to a child, record parent[child] = node. Now each node has three neighbours instead of two: left child, right child, and parent. The tree has become an ordinary graph where every edge can be walked both ways.

Piece two: a queue for breadth-first search, plus a visited set. Start the queue with the target node at distance 0. Pop a node; for each of its three neighbours that exists and has not been visited, mark it visited and push it with distance + 1. The visited set is essential now: because edges go both ways, without it you would walk from 5 to 3 and straight back to 5 forever.

Piece three: stop reading at distance k. Every node popped with distance exactly k is an answer; there is no need to push its neighbours.

Answer: [7, 4, 1].

Why it is correct

Adding parent pointers does not change which nodes are connected; it only lets you walk the existing edges upward as well as downward. So distances between nodes in the graph are the same as in the drawn tree. BFS on an unweighted graph pops nodes in order of distance from the start, and the first time a node is seen is along a shortest path, so each node's recorded distance is its true distance.

neighbours(v) = { left(v), right(v), parent(v) }, each walked once thanks to the visited set

A tree has no cycles, so the visited set only ever blocks the one step that would go straight back to where we came from.

Why it is fast

Building the parent map visits each node once. The BFS pushes and pops each node at most once, checking three neighbours each time, so about 3n checks. Total O(n) time and O(n) memory for the map and the queue. Stopping at distance k usually makes it far less than n in practice.

How to recognise it in an interview

Any time the walk must go up: "all nodes at distance k from a target", "how long until the whole tree burns from a start node", "directions from one node to another", "the closest leaf to a node". Say: "A tree only points down, so I will record parents in one pass and then BFS treating the tree as a graph with three neighbours per node." All Nodes Distance K in Binary Tree is the direct case. Amount of Time for Binary Tree to Be Infected is the same BFS run to the end; the answer is the largest distance reached. Step-By-Step Directions From a Binary Tree Node to Another uses the parent map to climb to the common ancestor with U moves, then descends with L and R moves.

02The idea in one line

Record parents, then BFS/DFS in every direction including upward.

Reach for it when: All nodes distance k, burn tree, closest leaf, step-by-step directions.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Distance 2 from node 5 in [3,5,1,6,2,0,8,null,null,7,4]. These are its captions in order, so you can follow without the video or check a step you missed.

1. A tree only points down; distance-k needs to walk up too
2. First pass: store each node's parent, so we can also walk up
3. Start BFS at the target 5 with distance 0
4. Pop 5 at 0: push unseen neighbours 6, 2, 3 at distance 1
5. Pop 6 at 1: push unseen neighbours at distance 2
6. Pop 2 at 1: push unseen neighbours 7, 4 at distance 2
7. Pop 3 at 1: push unseen neighbours 1 at distance 2
8. Node 7 is at distance 2: collect it
9. Node 4 is at distance 2: collect it
10. Node 1 is at distance 2: collect it
11. Distance 2 from 5: [7, 4, 1]
12. Parent map + BFS: O(n)

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree DP: take or skip this node, Serialize / deserialize by BFS.