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.
Amount of Time for Binary Tree to Be Infected
Core idea: An infection that spreads to every adjacent node each minute doesn't care that the structure is a tree — it cares about distance. The total time is simply the distance from
startto the farthest node. The catch: in a binary tree "adjacent" means children and the parent, so spread goes up as well as down. Add parent links to make the tree an undirected graph, then BFS out fromstart; the answer is the number of BFS rings minus one.
1. The problem, in a fresh setting
A juicy rumor starts at one person in an office org chart. Every minute, anyone who knows it tells everyone directly connected to them — their reports and their manager. How many minutes until the whole company has heard it?
That is exactly LeetCode 2385. You're given the root of a binary tree where every node has a unique value, and an integer start. At minute 0 only the node valued start is infected. Each minute, every infected node infects all of its adjacent nodes — its left child, its right child, and its parent. Return the number of minutes until every node is infected.
Picture a tiny tree and where the rumor begins:
| Minute | Who just heard it | Newly infected | Everyone infected? |
|---|---|---|---|
| 0 | (start) | 2 |
no — 1,3,4 still clean |
| 1 | 2 tells parent 1 and child 4 |
1, 4 |
no — 3 still clean |
| 2 | 1 tells its other child 3 |
3 |
yes |
Answer: 2 minutes. Notice the infection moved up from 2 to 1 and then back down to 3 — a path a "go down only" view of the tree would completely miss.
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