Skip to main content
Talentd

Reorder Routes to Make All Paths Lead to the City Zero - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchGraph15 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach city 0 after reorder.

 

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2:

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

 

Constraints:

  • 2 <= n <= 5 * 104
  • connections.length == n - 1
  • connections[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

Approach Overview

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.

Approach 1: Using Depth First Search (DFS)

To solve this problem, we can use a Depth First Search (DFS) starting from the capital city (city 0). During this traversal, we'll count the roads that need to be reordered.

We perform a DFS from city 0. For every road from a city a to b, we check if it's currently directed from 0 to n-1. If so, we need to count it as a reordering. Otherwise, we just traverse further.

We initialize an adjacency list to store each city's connections, differentiating directed and undirected edges. Starting from city 0, for each adjacent city, if the edge is directed away from the current city, we count it. We use a recursive DFS function to traverse the graph, keeping track of the parent to avoid cycles.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the number of cities, as each node is visited exactly once.

Space Complexity: O(n), the space used for the recursion stack and storing the graph structure.

Try this approach in the editor →

Approach 2: Breadth First Search (BFS)

An alternate approach using BFS begins at the capital city 0. We iterate over the child nodes, making direction checks immediately. This iterative form may help memory constraints on deep trees. We change direction whenever a node is reached by an edge that has to be flipped to reach city 0.

We use a queue to facilitate BFS traversal starting from city 0. While traversing, any edge that is oriented in the non-desired direction is counted. Each node is visited only once, avoiding cycles and performing necessary reorientation counting ‘on the fly’.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n) - due to a systematic BFS on each city.

Space Complexity: O(n) due to additional space for visited nodes and queued elements.

Try this approach in the editor →

Approach 3: DFS

The route map given in the problem has n nodes and n-1 edges. If we ignore the direction of the edges, then these n nodes form a tree. The problem requires us to change the direction of some edges so that each node can reach node 0.

We might as well consider starting from node 0 and reaching all other nodes. The direction is opposite to the problem description, which means that when we build the graph, for the directed edge [a, b], we should regard it as the directed edge [b, a]. That is to say, if it is from a to b, we need to change the direction once; if it is from b to a, no direction change is needed.

Next, we only need to start from node 0, search all other nodes, and during the process, if we encounter an edge that needs to change direction, we accumulate the number of direction changes once.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the problem.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: BFS

We can use the Breadth-First Search (BFS) method, starting from node 0, to search all other nodes. During the process, if we encounter an edge that requires a change of direction, we increment the count of direction changes.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the problem.

Code

Python

Python

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Depth First Search (DFS)

Time Complexity: O(n), where n is the number of cities, as each node is visited exactly once.

Space Complexity: O(n), the space used for the recursion stack and storing the graph structure.

Breadth First Search (BFS)

Time Complexity: O(n) - due to a systematic BFS on each city.

Space Complexity: O(n) due to additional space for visited nodes and queued elements.

DFS—
BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Edge Direction TrackingO(n)O(n)Most common interview solution. Concise recursion and natural tree traversal.
BFS with Direction FlagsO(n)O(n)Useful when preferring iterative traversal or avoiding recursion depth issues.

Video Solution

Leetcode 1466 - REORDER ROUTES TO MAKE ALL PATHS LEAD TO THE CITY ZERO • NeetCode • 62,215 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reorder Routes to Make All Paths Lead to the City Zero easy or hard?
The problem is classified as Medium on LeetCode. The main difficulty is recognizing that the graph forms a tree and modeling edge direction so traversal can detect which roads need reversal. Once the adjacency list with direction flags is built, the solution becomes a straightforward DFS or BFS with O(n) complexity.
Reorder Routes to Make All Paths Lead to the City Zero Python/Java solution
Python implementations typically use DFS with recursion and adjacency lists built using dictionaries or lists. Java solutions often use BFS with a queue and ArrayList-based adjacency lists. Both implementations follow the same idea of storing direction flags and counting edges that must be reversed during traversal.
How to solve Reorder Routes to Make All Paths Lead to the City Zero in O(n)?
Construct an adjacency list that stores both directions for every road with a direction flag. Run DFS or BFS starting from city 0 and traverse the entire tree. Whenever you move along an edge that originally goes away from the current node, increment the reversal count. Because the graph is a tree with n-1 edges, this traversal processes each edge once, achieving O(n) time.
What is the best approach for Reorder Routes to Make All Paths Lead to the City Zero?
The optimal approach is graph traversal using DFS or BFS while tracking edge direction. Build an adjacency list that stores both directions of every road along with a flag indicating whether the edge needs reversal. Starting from city 0, traverse the graph and count edges that originally point away from the capital. This solution runs in O(n) time and O(n) space.
Is Reorder Routes to Make All Paths Lead to the City Zero asked at Google/Amazon/Meta?
Graph traversal problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The problem tests your understanding of graph modeling, tree traversal, and edge direction handling using DFS or BFS. Variations involving edge reversals and reachability are common in system design and algorithm interviews.
What data structure is used in Reorder Routes to Make All Paths Lead to the City Zero?
The primary data structure is an adjacency list representing the graph. Each entry stores a neighbor and a flag indicating whether the road direction needs reversal. A visited set or boolean array prevents revisiting nodes during DFS or BFS traversal.
What is the time complexity of Reorder Routes to Make All Paths Lead to the City Zero?
The optimal DFS or BFS solution runs in O(n) time where n is the number of cities. Each city is visited once and each road is processed once during traversal. The space complexity is O(n) due to the adjacency list and the recursion stack or queue used during traversal.

Ready to solve this problem?

Practice Reorder Routes to Make All Paths Lead to the City Zero with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Edge Reversals So Every Node Is Reachable