Reorder Routes to Make All Paths Lead to the City Zero - Video Solutions

Problem Overview: You are given n cities connected by n - 1 directed roads forming a tree. Some roads point away from city 0. The goal is to reverse the minimum number of roads so every city has a path leading to city 0. The core challenge is detecting which edges point in the wrong direction when traversing from the capital.

Approach 1: Depth First Search (DFS) with Edge Direction Tracking (O(n) time, O(n) space)

Convert the directed graph into an adjacency list that keeps track of edge directions. For each connection (u, v), store two entries: (u → v, needsReversal = 1) and (v → u, needsReversal = 0). This representation allows traversal in both directions while remembering whether the original edge pointed away from city 0. Start a DFS from node 0, visiting neighbors while avoiding the parent node. Each time DFS follows an edge marked with needsReversal = 1, increment the counter because that road must be reversed to allow travel toward the capital.

This works because the underlying structure is a tree, so every edge is visited exactly once. DFS naturally explores the entire graph while accumulating the number of incorrect directions. The approach relies on standard Depth-First Search traversal over a graph representation.

Approach 2: Breadth First Search (BFS) with Direction Flags (O(n) time, O(n) space)

The BFS approach uses the same adjacency representation but processes nodes level by level starting from city 0. Initialize a queue with node 0 and mark it visited. For each node dequeued, iterate through its neighbors. If the stored direction flag indicates the edge originally pointed away from the current node toward the neighbor, it must be reversed, so increment the counter.

Each neighbor is then added to the queue if it has not been visited. Because the graph is a tree with n - 1 edges, BFS visits each node once and inspects each edge once, resulting in linear time. This version is often easier to reason about when you prefer iterative traversal using a queue. It follows the classic pattern of Breadth-First Search on graphs while tracking edge orientation.

Recommended for interviews: Both DFS and BFS achieve the optimal O(n) time complexity since every node and edge is processed once. Interviewers typically expect the DFS solution because it is concise and demonstrates strong understanding of graph traversal and edge direction modeling. Showing the adjacency trick (storing both directions with a cost flag) demonstrates that you can convert a directed tree into a traversal-friendly structure. BFS is equally valid and often preferred in iterative implementations.