1466 · Reorder Routes to Make All Paths Lead to City Zero

There are n cities and n - 1 directed roads forming a tree. Reorient the minimum number of roads so that every city can reach city 0.

Tree Traversal & Road Orientations

idle

INVARIANT Tree Outward Traversal Invariant: Root the tree at city 0. For any edge (u, v), if the road points away from 0 during traversal (from parent to child), it must be reversed (cost +1). If it points toward 0 (from child to parent), cost is 0. Running time is O(n), Space is O(n).

Roads Reversed:0

Current City:0

Visited:[0]

Press Run to begin.

0 / 0

Java 21 Solution

INTERVIEW SCRIPT

How to Explain Reorder Routes to City Zero

1. Invert the Question

"Instead of checking if every city can reach 0, start at city 0 and traverse outward to all nodes. The tree structure guarantees every node is reachable via a unique path."

2. Bi-directional Adjacency Representation

"Store neighbors as pairs: (neighbor, sign). When adding road $u \to v$, store $(v, 1)$ in $u$'s list (meaning road points away from $u$) and $(u, 0)$ in $v$'s list (meaning road points toward $v$)."

3. DFS Traversal & Counting

"Run DFS from 0 with a parent tracker or visited array. When moving from current city $u$ to child $v$, add the sign to our answer: if sign is 1, the original road points $u \to v$ (away from 0) and must be flipped!"

4. Linear Complexity

"Every node and edge in the tree is traversed exactly once. Time is $O(n)$ and space is $O(n)$ for the adjacency list and recursion stack."