Reorder Routes to Make All Paths Lead to City Zero: BFS on Directed Trees

You are given n cities numbered 0 to n-1, connected by n-1 directed roads that form a tree. The roads were designed so that there is exactly one path between any two cities (ignoring direction). Your task is to reorder the minimum number of roads so that every city can reach city 0. Return the number of roads you need to reverse.

This is LeetCode 1466: Reorder Routes to Make All Paths Lead to the City Zero.

Why this problem matters

Tree problems with directed edges show up regularly in interviews, and this one isolates a critical skill: reasoning about edge direction relative to a root. You are not asked to find a path or detect a cycle. You are asked to figure out which edges point the wrong way. That requires you to think about direction from a specific reference point, which is a different mental model than the typical "can I reach node X?" traversal.

This problem also reinforces the technique of converting a directed graph into an undirected adjacency list with direction metadata. Many tree and graph problems require you to traverse edges in both directions while still knowing the original orientation. Once you learn this trick here, you will use it in problems involving rerooting trees, finding subtree properties, and processing edges relative to arbitrary roots.

The BFS/DFS approach here runs in linear time and visits each node exactly once. It is a clean, elegant solution that rewards understanding the structure of trees rather than brute-forcing all possible reorderings.

The key insight

Since the cities form a tree with n-1 edges, there is exactly one undirected path between any two cities. To make every city reach city 0, every edge on the path from any city to 0 must point toward 0. That means any edge pointing away from 0 (in the direction from parent to child, when 0 is the root) needs to be reversed.

The trick is to build an undirected adjacency list where each entry records whether the original directed edge goes "parent to child" or "child to parent" relative to your traversal from node 0. You traverse from 0 outward using BFS or DFS. For each neighbor you visit, you check: does the original edge point from the current node to the neighbor (away from 0)? If so, that edge needs reversal. If the original edge points from the neighbor to the current node (toward 0), it is already correct.

You count every edge that points away from 0 during the traversal. That count is your answer.

The solution

from collections import deque, defaultdict

def min_reorder(n: int, connections: list[list[int]]) -> int:
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append((v, True))
        graph[v].append((u, False))

    visited = set([0])
    queue = deque([0])
    count = 0

    while queue:
        city = queue.popleft()
        for neighbor, is_original in graph[city]:
            if neighbor not in visited:
                visited.add(neighbor)
                if is_original:
                    count += 1
                queue.append(neighbor)

    return count

Let's walk through what each piece does.

First, we build an undirected adjacency list from the directed connections. For each original edge [u, v], we add (v, True) to graph[u] and (u, False) to graph[v]. The boolean flag True means "this is the original direction" and False means "this is the reverse direction we added for traversal."

The BFS starts from city 0. For each city we dequeue, we look at all its neighbors. If a neighbor has not been visited, we visit it and check the direction flag. If is_original is True, the original edge points from the current city to the neighbor, meaning it points away from 0. That edge needs reversal, so we increment count. If is_original is False, the original edge points from the neighbor toward the current city, which is toward 0. That edge is already correct.

Since the graph is a tree, each node is visited exactly once, and every edge is examined exactly twice (once from each endpoint). The total number of reversals is the answer.

Visual walkthrough

Let's trace through the example with n=6 and connections=[[0,1],[1,3],[2,3],[4,0],[4,5]]. Watch how BFS radiates from city 0 and counts edges that point the wrong way.

The BFS visits every city exactly once. Each time it discovers an edge pointing away from 0 (the original direction goes from parent to child in the BFS tree), it counts a reversal. Edges pointing toward 0 are already correct and contribute nothing to the count. The final answer is 3.

Complexity analysis

Time is O(n). Building the adjacency list iterates through all n-1 edges once. The BFS visits each of the n nodes exactly once and examines each edge twice (once from each endpoint). All operations are O(n) total.

Space is O(n). The adjacency list stores two entries per edge, so 2*(n-1) entries total, which is O(n). The visited set and BFS queue each hold at most n elements. Total auxiliary space is O(n).

The building blocks

1. Undirected adjacency list with direction metadata

The technique of adding both directions of a directed edge to an adjacency list, while tagging which one is the original, is the foundation of this solution.

graph = defaultdict(list)
for u, v in connections:
    graph[u].append((v, True))
    graph[v].append((u, False))

This pattern appears whenever you need to traverse a directed graph as if it were undirected but still reason about the original edge directions. You will see it in problems involving rerooting, edge classification, and tree DP where direction matters.

2. BFS with conditional counting

Standard BFS explores all reachable nodes. Here, you add a condition during exploration: check a property of the edge you are traversing and accumulate a count based on it.

for neighbor, is_original in graph[city]:
    if neighbor not in visited:
        visited.add(neighbor)
        if is_original:
            count += 1
        queue.append(neighbor)

This "BFS with edge-property counting" pattern generalizes to any problem where you need to count or sum something as you traverse. The traversal structure stays the same. You just add logic inside the neighbor loop.

Edge cases

• n=2, single edge pointing away from 0. connections=[[0,1]]. The edge goes from 0 to 1 (away from 0). One reversal needed. Returns 1.
• n=2, single edge pointing toward 0. connections=[[1,0]]. The edge goes from 1 to 0 (toward 0). Already correct. Returns 0.
• Star graph, all edges pointing away. City 0 connects directly to all other cities via edges [0,1], [0,2], ..., [0,n-1]. Every edge needs reversal. Returns n-1.
• Star graph, all edges pointing toward 0. connections=[[1,0],[2,0],...,[n-1,0]]. Every edge already points toward 0. Returns 0.

From understanding to recall

You have seen how the direction-tagged adjacency list and a single BFS pass solve this problem cleanly. The logic is compact: build the graph with flags, traverse from 0, count edges that point the wrong way. But reproducing it under pressure requires you to remember several small details. Which direction gets True? Do you check is_original or not is_original? Do you add the neighbor to visited before or after enqueueing?

These are the kinds of details that spaced repetition locks in. You practice writing the adjacency list construction and the BFS counting loop from scratch at increasing intervals. After a few rounds, you stop thinking about the details. You just write the code.

Related posts

• Course Schedule - Directed graph traversal with topological sort, another pattern for reasoning about edge direction
• Number of Islands - BFS/DFS on grids, the foundational traversal pattern that this problem extends to trees
• Clone Graph - Graph traversal with neighbor processing, reinforcing the adjacency list and visited set pattern

CodeBricks breaks Reorder Routes into its direction-tagged adjacency list and BFS counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a directed tree problem shows up in your interview, you do not hesitate. You just write it.