Tree as a Graph
What is this?
A tree normally only knows how to point downward — every node knows its children but not its parent, like a one-way street. Some problems need you to travel up toward the parent as well, such as finding the nearest exit or how fast something spreads. The fix is simple: add links back up so every connection works both ways, turning the tree into a free-roaming map (a graph). Then you just explore it normally.
💡 Fun fact: A tree is really just a graph with no loops, so adding parent links doesn't break anything — it simply unlocks the full toolbox of graph techniques on the same data.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: A binary tree only stores child pointers — you can go down, never up. The moment a problem lets you move toward the parent as well (nearest/farthest, time-to-spread), the tree's pointers aren't enough. The fix: add parent edges to make it an undirected graph, then run plain BFS. "I can move up" is the signal to convert.
The conversion
Build adjacency once (each node ↔ its children and its parent), then BFS from the source. The structure becomes a graph; the distance metric becomes ordinary BFS distance.
The problems
- Closest Leaf in a Binary Tree — BFS from the target until the first leaf; the closest leaf may be reached by going up then down.
- Amount of Time for Binary Tree to Be Infected — infection spreads to all neighbors each minute; the answer is the max graph distance from the start node.
Key takeaways
- Child-only pointers can't go up — add parent edges to make the tree undirected.
- "Move toward the parent" / "spread to neighbors" ⇒ tree-as-graph + BFS.
- Nearest = first BFS hit; farthest = last BFS level (eccentricity from the source).
- Build adjacency once, then the problem is a standard graph BFS.
- Why interviewers love it: it tests whether you recognize when a tree's own structure stops being enough.
Order: Closest Leaf in a Binary Tree → Amount of Time for Binary Tree to Be Infected.
Closest Leaf in a Binary Tree
Core idea: The trick is the word nearest. In a binary tree you can normally only walk down (parent → child), but the closest leaf to your target might be reached by walking up to a parent and then back down a different branch. A tree only stores child pointers, so down-only search physically cannot make that turn. The fix: treat the tree as an undirected graph — give every node an edge to its children and an edge back to its parent — then run a plain BFS from the target. BFS expands in rings of increasing edge-distance, so the first leaf it dequeues is the closest leaf. (A leaf here = a node from the original tree with no children.)
1. The problem, in a fresh setting
You're standing somewhere inside a multi-floor office building whose layout happens to be a binary tree: each room connects up to one corridor (its parent) and down to at most two rooms (its children). Some rooms are dead ends — rooms with no further rooms below them. You are in the room labelled k, and you want the nearest dead-end exit, counting one "hop" per doorway you pass through. Crucially, you're allowed to walk back up the corridor toward the lobby and then descend a different branch if that gets you to a dead end sooner.
Formally: given the root of a binary tree where every node has a distinct value, and a target value k, return the value of the leaf nearest to the node whose value is k. Distance is the number of edges on the path, and the path may travel up to a parent as well as down to children. A leaf is a node with no left and no right child.
Here is a small tree and the target k = 1:
Target k |
Candidate leaves & their edge-distance from k |
Answer |
|---|---|---|
1 |
4 is 2 hops (1→3→4); 2 is 1 hop (1→2) |
2 |
The leaf 2 wins because it's a single hop down. Note 4 is also a leaf but two hops away. Easy so far — the down-only intuition still works here. The interesting cases are when the nearest leaf lives above the target.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson