LeetCode 2858 - Minimum Edge Reversals So Every Node Is Reachable

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

This problem gives us a directed graph with n nodes and exactly n - 1 edges. The important guarantee is that if we ignore the direction of every edge, the graph becomes a tree. That means the underlying structure is connected and acyclic.

Each edge is currently directed one way. For every node i, we want to determine the minimum number of edge reversals needed so that starting from node i, we can reach every other node following directed edges.

An edge reversal means changing:

u -> v

into:

v -> u

The reversals for one starting node do not affect the result for another starting node. Each node is evaluated independently.

The output is an array answer where:

answer[i] = minimum reversals needed so node i can reach all other nodes

Because the underlying graph is a tree, there is exactly one undirected path between any two nodes. This property is extremely important because it means the direction of each edge uniquely determines whether traversal is possible along that path.

The constraints are large:

n can be up to 100000
There are n - 1 edges

This immediately tells us that an O(n^2) solution will be too slow. We need something close to linear time.

Several edge cases are important:

A graph where all edges already point away from one node, meaning that node requires 0 reversals.
A chain where every edge points toward one end, forcing many reversals for certain roots.
Small trees with only two nodes.
Deep trees where recursive DFS may hit recursion limits in Python if not handled carefully.

The tree guarantee also simplifies the problem significantly because we never need to deal with cycles or multiple possible routes.

Approaches

Brute Force Approach

A brute force solution would independently compute the answer for every node.

For a chosen starting node root, we could perform a DFS or BFS over the undirected version of the tree. Whenever we traverse an edge in the same direction as the original edge, no reversal is needed. Whenever we traverse against the original direction, we count one reversal.

More concretely:

Treat every edge as bidirectional for traversal.
Store whether traversing from u to v matches the original direction.
For every node:
Run DFS/BFS from that node.
Count how many edges must be reversed so all traversal directions point outward from the chosen root.

This works because a rooted tree requires every edge to point away from the root for full reachability.

The issue is complexity. Running a traversal from every node costs:

O(n) per root × n roots = O(n^2)

With n = 100000, this is far too slow.

Optimal Approach

The key observation is that answers for neighboring roots are closely related.

Suppose we already know the answer for node u.

Now imagine rerooting the tree at a neighbor v.

Only one edge changes its contribution:

If the original edge is u -> v:
It was correctly directed when rooted at u
It becomes incorrectly directed when rooted at v
Answer increases by 1
If the original edge is v -> u:
It was incorrect when rooted at u
It becomes correct when rooted at v
Answer decreases by 1

This allows us to compute all answers using two DFS traversals:

First DFS computes the answer for root 0
Second DFS reroots dynamically to compute answers for all nodes

This is a classic rerooting DP technique on trees.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Run DFS/BFS from every node independently
Optimal	O(n)	O(n)	Use rerooting DP with two DFS traversals

Algorithm Walkthrough

Step 1: Build an Augmented Adjacency List

We need to traverse the tree in both directions, but we also need to know whether traversing an edge requires reversal.

For every original directed edge:

u -> v

we add:

(v, 0) to u
Traversing from u to v needs no reversal
(u, 1) to v
Traversing from v to u requires reversing the edge

Here:

0 means no reversal needed
1 means reversal needed

This representation allows us to treat the graph as undirected during DFS while still tracking reversal costs.

Step 2: Compute the Answer for Root 0

We run a DFS starting from node 0.

Whenever we traverse an edge marked with cost 1, it means the edge points toward the root instead of away from it, so it must be reversed.

The total number of such edges gives:

answer[0]

Step 3: Reroot the Tree

Now we compute answers for all other nodes.

Suppose we move the root from u to neighbor v.

There are two cases:

Original edge was u -> v

Then:

It was correct for root u
It becomes wrong for root v

So:

answer[v] = answer[u] + 1

Original edge was v -> u

Then:

It was wrong for root u
It becomes correct for root v

So:

answer[v] = answer[u] - 1

Using our stored costs:

cost == 0 means original direction u -> v
cost == 1 means original direction v -> u

So:

if cost == 0:
    answer[v] = answer[u] + 1
else:
    answer[v] = answer[u] - 1

Step 4: Continue DFS

We recursively propagate answers throughout the tree.

Since each edge is processed a constant number of times, the total complexity remains linear.

Why it works

The algorithm works because rerooting only changes the status of one edge, the edge between the old root and new root.

All other edges preserve their relative orientation with respect to the root. Therefore, when moving the root across an edge:

One edge either becomes correct instead of incorrect
Or incorrect instead of correct

This local transition allows every answer to be derived from its parent in constant time.

Because the graph is a tree, there is exactly one path between nodes, so every edge has a unique contribution to reachability.

Python Solution

from typing import List
import sys

sys.setrecursionlimit(1 << 20)

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append((v, 0))
            graph[v].append((u, 1))

        answer = [0] * n

        def dfs1(node: int, parent: int) -> int:
            reversals = 0

            for neighbor, cost in graph[node]:
                if neighbor == parent:
                    continue

                reversals += cost
                reversals += dfs1(neighbor, node)

            return reversals

        answer[0] = dfs1(0, -1)

        def dfs2(node: int, parent: int) -> None:
            for neighbor, cost in graph[node]:
                if neighbor == parent:
                    continue

                if cost == 0:
                    answer[neighbor] = answer[node] + 1
                else:
                    answer[neighbor] = answer[node] - 1

                dfs2(neighbor, node)

        dfs2(0, -1)

        return answer

The implementation begins by constructing an adjacency list that stores both neighbors and reversal costs.

For every original edge u -> v:

Moving from u to v costs 0
Moving from v to u costs 1

The first DFS computes the number of reversals needed when node 0 is the root. Every edge that points toward the root contributes one reversal.

The second DFS performs rerooting DP. When moving the root across an edge:

If the edge originally points away from the current node, the new root needs one additional reversal.
Otherwise, the new root needs one fewer reversal.

The recursion limit is increased because the tree may become a long chain of length 100000.

Go Solution

package main

func minEdgeReversals(n int, edges [][]int) []int {
	graph := make([][][2]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]

		graph[u] = append(graph[u], [2]int{v, 0})
		graph[v] = append(graph[v], [2]int{u, 1})
	}

	answer := make([]int, n)

	var dfs1 func(int, int) int

	dfs1 = func(node int, parent int) int {
		reversals := 0

		for _, next := range graph[node] {
			neighbor := next[0]
			cost := next[1]

			if neighbor == parent {
				continue
			}

			reversals += cost
			reversals += dfs1(neighbor, node)
		}

		return reversals
	}

	answer[0] = dfs1(0, -1)

	var dfs2 func(int, int)

	dfs2 = func(node int, parent int) {
		for _, next := range graph[node] {
			neighbor := next[0]
			cost := next[1]

			if neighbor == parent {
				continue
			}

			if cost == 0 {
				answer[neighbor] = answer[node] + 1
			} else {
				answer[neighbor] = answer[node] - 1
			}

			dfs2(neighbor, node)
		}
	}

	dfs2(0, -1)

	return answer
}

The Go implementation follows the same structure as the Python solution.

A slice of pairs is used for the adjacency list. Each pair stores:

Neighbor node
Reversal cost

Go does not have recursion depth protection like Python, so extremely deep trees could theoretically risk stack overflow in some environments. However, LeetCode's Go environment generally accepts recursive DFS for this problem size.

Slices are dynamically resized, making them a natural fit for adjacency lists.

Worked Examples

Example 1

n = 4
edges = [[2,0],[2,1],[1,3]]

Step 1: Build Graph

Original Edge	Stored Entries
2 -> 0	2:(0,0), 0:(2,1)
2 -> 1	2:(1,0), 1:(2,1)
1 -> 3	1:(3,0), 3:(1,1)

Step 2: Compute answer[0]

DFS from node 0.

Traversal	Cost
0 -> 2	1
2 -> 1	0
1 -> 3	0

Total reversals:

So:

answer[0] = 1

Step 3: Reroot

Move from 0 to 2.

Edge 2 -> 0 originally points toward 0.

Moving root to 2 fixes this edge:

answer[2] = answer[0] - 1 = 0

Move from 2 to 1.

Edge 2 -> 1 originally points away from 2.

Moving root to 1 makes it incorrect:

answer[1] = answer[2] + 1 = 1

Move from 1 to 3.

Edge 1 -> 3 originally points away from 1.

Moving root to 3 makes it incorrect:

answer[3] = answer[1] + 1 = 2

Final result:

[1,1,0,2]

Example 2

n = 3
edges = [[1,2],[2,0]]

Step 1: Build Graph

Original Edge	Stored Entries
1 -> 2	1:(2,0), 2:(1,1)
2 -> 0	2:(0,0), 0:(2,1)

Step 2: Compute answer[0]

DFS from 0.

Traversal	Cost
0 -> 2	1
2 -> 1	1

Total:

So:

answer[0] = 2

Step 3: Reroot

Move root from 0 to 2.

Edge 2 -> 0 becomes correct:

answer[2] = 2 - 1 = 1

Move root from 2 to 1.

Edge 1 -> 2 becomes correct:

answer[1] = 1 - 1 = 0

Final result:

[2,0,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each edge is processed a constant number of times
Space	O(n)	Adjacency list and recursion stack both require linear space

The graph contains exactly n - 1 edges because it is a tree. Both DFS traversals visit every node and edge once.

The adjacency list stores two directed entries per edge, so storage remains linear.

The recursion stack may reach depth n in a degenerate chain-shaped tree.

Test Cases

from typing import List

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append((v, 0))
            graph[v].append((u, 1))

        answer = [0] * n

        def dfs1(node: int, parent: int) -> int:
            total = 0

            for neighbor, cost in graph[node]:
                if neighbor == parent:
                    continue

                total += cost
                total += dfs1(neighbor, node)

            return total

        answer[0] = dfs1(0, -1)

        def dfs2(node: int, parent: int):
            for neighbor, cost in graph[node]:
                if neighbor == parent:
                    continue

                if cost == 0:
                    answer[neighbor] = answer[node] + 1
                else:
                    answer[neighbor] = answer[node] - 1

                dfs2(neighbor, node)

        dfs2(0, -1)

        return answer

solution = Solution()

assert solution.minEdgeReversals(
    4,
    [[2,0],[2,1],[1,3]]
) == [1,1,0,2]  # Example 1

assert solution.minEdgeReversals(
    3,
    [[1,2],[2,0]]
) == [2,0,1]  # Example 2

assert solution.minEdgeReversals(
    2,
    [[0,1]]
) == [0,1]  # Smallest non-trivial tree

assert solution.minEdgeReversals(
    2,
    [[1,0]]
) == [1,0]  # Reverse orientation of previous case

assert solution.minEdgeReversals(
    5,
    [[0,1],[1,2],[2,3],[3,4]]
) == [0,1,2,3,4]  # Straight outward chain

assert solution.minEdgeReversals(
    5,
    [[1,0],[2,1],[3,2],[4,3]]
) == [4,3,2,1,0]  # Straight inward chain

assert solution.minEdgeReversals(
    5,
    [[0,1],[2,0],[2,3],[4,2]]
) == [2,3,1,2,0]  # Mixed orientations

assert solution.minEdgeReversals(
    6,
    [[0,1],[0,2],[0,3],[0,4],[0,5]]
) == [0,1,1,1,1,1]  # Star centered at 0

assert solution.minEdgeReversals(
    6,
    [[1,0],[2,0],[3,0],[4,0],[5,0]]
) == [5,4,4,4,4,4]  # All edges point toward center

Test	Why
Example 1	Validates core rerooting behavior
Example 2	Validates multiple reversal propagation
Two nodes outward	Smallest valid tree
Two nodes inward	Ensures reversal counting works
Outward chain	Best-case orientation
Inward chain	Worst-case orientation
Mixed tree	Tests irregular structures
Outward star	Root already reaches all nodes
Inward star	Many nodes require large reversals

Edge Cases

Deep Linear Tree

A chain-shaped tree like:

0 -> 1 -> 2 -> 3 -> ...

creates maximum recursion depth and maximum answer variation.

This can expose recursion depth issues in Python. The implementation handles this by increasing the recursion limit using:

sys.setrecursionlimit(1 << 20)

Without this adjustment, Python could raise a recursion error on large inputs.

All Edges Point Toward One Node

Consider:

1 -> 0
2 -> 0
3 -> 0

Node 0 cannot reach anyone without reversing every edge.

This case is important because many edges contribute reversals simultaneously. The rerooting logic correctly decreases the answer when moving the root outward because edges become properly oriented.

Already Optimal Root

Some nodes may already reach every other node without reversals.

For example:

0 -> 1
0 -> 2
0 -> 3

Here:

answer[0] = 0

The algorithm handles this naturally because the first DFS counts only incorrectly directed edges. If none exist, the answer remains zero.

Smallest Possible Tree

When n = 2, there is only one edge.

This is easy to mishandle because there are no deeper recursive branches. The implementation correctly computes both possible orientations:

0 -> 1  => [0,1]
1 -> 0  => [1,0]

The adjacency representation and rerooting logic work even at the smallest valid size.