Find minimum reversals to orient edges away from root
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a connected graph with `n` nodes labeled `0..n-1` and `n-1` directed edges. If you ignore edge directions, the edges form a tree.
Each directed edge is given as a pair `(u, v)` meaning the edge currently points from `u` to `v`.
You are also given a root node `r`.
In the rooted tree (rooted at `r`), every edge should point **away from the root** (i.e., from parent to child). You may reverse the direction of any edge; each reversal costs `1`.
Return the minimum total number of edge reversals required so that, after reversals, all edges in the tree point away from `r`.
#### Input
- Integer `n`
- List of directed edges `edges`, length `n-1`, each as `(u, v)`
- Integer root `r`
#### Output
- Integer: minimum number of reversals
#### Example
Suppose `n = 5`, `r = 0`, and edges are:
- `(1, 0)`, `(0, 2)`, `(3, 2)`, `(3, 4)`
Ignoring directions, the tree is `0-1`, `0-2`, `2-3`, `3-4`.
To make all edges point away from `0`, edges `(1,0)` and `(3,2)` must be reversed, so the answer is `2`.
#### Constraints (typical)
- `1 <= n <= 2e5`
- The undirected version of `edges` is a tree
- Nodes are `0..n-1`
*Note:* With large `n`, recursive DFS may overflow the call stack in some languages; an iterative traversal may be required.
Quick Answer: This question evaluates understanding of directed graphs and rooted trees, the ability to reason about edge orientations and minimal reversals, and competency in traversal techniques and complexity analysis.
You are given a connected graph with `n` nodes labeled `0..n-1` and `n-1` directed edges. If you ignore edge directions, the edges form a tree.
Each directed edge is given as a pair `(u, v)` meaning the edge currently points from `u` to `v`.
You are also given a root node `r`.
In the rooted tree (rooted at `r`), every edge should point **away from the root** (i.e., from parent to child). You may reverse the direction of any edge; each reversal costs `1`.
Return the minimum total number of edge reversals required so that, after reversals, all edges in the tree point away from `r`.
#### Input
- Integer `n`
- List of directed edges `edges`, length `n-1`, each as `(u, v)`
- Integer root `r`
#### Output
- Integer: minimum number of reversals
#### Example
Suppose `n = 5`, `r = 0`, and edges are `(1, 0)`, `(0, 2)`, `(3, 2)`, `(3, 4)`. Ignoring directions, the tree is `0-1`, `0-2`, `2-3`, `3-4`. To make all edges point away from `0`, edges `(1,0)` and `(3,2)` must be reversed, so the answer is `2`.
*Note:* With large `n` (up to `2e5`), a single deep path can blow a recursive call stack — use an iterative BFS/DFS traversal.
Constraints
- 1 <= n <= 2 * 10^5
- edges.length == n - 1
- The undirected version of edges forms a tree (connected, acyclic)
- 0 <= u, v, r < n
- Each edge is a directed pair (u, v); input orientation may already be correct or reversed
Examples
Input: (5, [(1, 0), (0, 2), (3, 2), (3, 4)], 0)
Expected Output: 2
Explanation: The worked example. Edges (1,0) and (3,2) point toward root 0 along their branches, so both must be reversed.
Input: (1, [], 0)
Expected Output: 0
Explanation: A single node with no edges is already a valid rooted tree; nothing to reverse.
Hints
- Rooting the tree at r forces a unique target direction for every edge: parent -> child. There is no choice to optimize across edges, so the answer is just the count of edges whose current direction disagrees.
- Build an undirected adjacency list so you can walk the tree in any direction, but tag each entry with a cost: for original edge (u, v), add (v, 0) to adj[u] (forward = free) and (u, 1) to adj[v] (backward = one reversal).
- Traverse outward from r with BFS or an explicit stack and sum the cost tag of each edge crossed in the parent -> child direction. Use an iterative traversal — a recursive DFS can overflow the stack on a 2e5-deep path.