Minimum Edge Reversals So Every Node Is Reachable

Minimum Edge Reversals So Every Node Is Reachable

1. What is this problem about?

The Minimum Edge Reversals So Every Node Is Reachable is a sophisticated graph problem. You are given a directed tree (a graph with $N$ nodes and $N-1$ edges where there is exactly one path between any two nodes if edges were undirected). The goal is to find a root node such that the number of edge reversals needed to reach all other nodes from that root is minimized. You need to return an array where the $i$-th element is the minimum reversals needed if node $i$ is the root.

2. Why is this asked in interviews?

This problem is a favorite at companies like Uber, Google, and PhonePe because it tests advanced knowledge of Graph Theory and Dynamic Programming on trees. Specifically, it evaluates whether a candidate can use the "Re-rooting DP" technique. This technique is essential for problems where you need to calculate a property for every possible root in a tree without running an $O(N)$ traversal $N$ times.

3. Algorithmic pattern used

The primary algorithmic pattern is Dynamic Programming on Trees (Re-rooting technique).

1. First, we pick an arbitrary root (say node 0) and calculate the reversals needed for it using a standard DFS. During this, we treat original edges as cost 0 and "reversed" edges as cost 1.
2. Second, we perform another DFS to "shift" the root. If we move the root from node $u$ to an adjacent node $v$:
   • If the edge was $u \to v$, moving the root to $v$ means we now need to reverse $v \to u$, so the cost increases by 1 for some paths and decreases for others.
   • By observing the local change, we can calculate reversals(v) from reversals(u) in $O(1)$. This "Graph, DFS, Dynamic Programming interview pattern" allows solving the problem in $O(N)$ time.

4. Example explanation

Suppose $0 \to 1$ and $2 \to 1$.

• Root 0: Can reach 1 ($0 \to 1$, cost 0). To reach 2, must reverse $2 \to 1$ ($1 \to 2$, cost 1). Total = 1.
• Root 1: To reach 0, must reverse $0 \to 1$ (cost 1). To reach 2, must reverse $2 \to 1$ (cost 1). Total = 2.
• Root 2: Can reach 1 ($2 \to 1$, cost 0). To reach 0, must reverse $0 \to 1$ (cost 1). Total = 1. Result: [1, 2, 1].

5. Common mistakes candidates make

In the Minimum Edge Reversals So Every Node Is Reachable coding problem, the most common error is attempting to run a BFS/DFS from every single node, resulting in an $O(N^2)$ complexity which is too slow for $N=10^5$. Another mistake is failing to correctly track which edges are "real" and which are "artificial" (added to allow undirected traversal). Candidates also struggle with the re-rooting logic, specifically how the cost changes when the edge between the old root and new root is reversed.

6. Interview preparation tip

Master the "Re-rooting DP" pattern. It is the gold standard for tree problems where the answer depends on the root. Practice on problems like "Sum of Distances in Tree" first, as it uses the same underlying logic. Understanding how to transfer a global result from a parent to a child based only on the edge connecting them is a high-level skill that will impress any interviewer at a top tech company.