You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
You are also given two binary strings start and target of length n. For each node x, start[x] is its initial color and target[x] is its desired color.
In one operation, you may pick an edge with index i and toggle both of its endpoints. That is, if the edge is [u, v], then the colors of nodes u and v each flip from '0' to '1' or from '1' to '0'.
Return an array of edge indices whose operations transform start into target. Among all valid sequences with minimum possible length, return the edge indices in increasing order.
If it is impossible to transform start into target, return an array containing a single element equal to -1.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], start = "010", target = "100"
Output: [0]
Explanation:
Toggle edge with index 0, which flips nodes 0 and 1.
The string changes from "010" to "100", matching the target.
Example 2:
Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]], start = "0011000", target = "0010001"
Output: [1,2,5]
Explanation:
After these operations, the resulting string becomes "0010001", which matches the target.
Example 3:
Input: n = 2, edges = [[0,1]], start = "00", target = "01"
Output: [-1]
Explanation:
There is no sequence of edge toggles that transforms "00" into "01". Therefore, we return [-1].
Constraints:
2 <= n == start.length == target.length <= 105edges.length == n - 1edges[i] = [ai, bi]0 <= ai, bi < nstart[i] is either '0' or '1'.target[i] is either '0' or '1'.edges represents a valid tree.Problem Overview: You are given a tree where edges have an orientation or state. You can toggle an edge (reverse its direction). The goal is to compute the minimum number of toggles needed so the tree satisfies the required orientation constraint relative to a chosen root.
Approach 1: Try Every Root with DFS (Brute Force) (Time: O(n2), Space: O(n))
Treat each node as a potential root. For a chosen root, run a DFS across the tree and count how many edges violate the desired orientation (for example, edges pointing toward the parent instead of away). Each violation requires one toggle. Because the graph is a tree, DFS visits all n-1 edges and computes the cost for that root in O(n). Repeating this for all n nodes leads to O(n^2) time. This approach is straightforward and helps reason about how edge directions affect the total cost, but it becomes too slow for large trees.
Approach 2: DFS with Rerooting (Optimal) (Time: O(n), Space: O(n))
The optimal solution computes the cost for one root, then efficiently propagates results to all other nodes using a rerooting technique. First, build an adjacency list that stores both neighbors and whether traversing the edge requires a toggle. Run an initial DFS from node 0 to count how many edges must be toggled so every edge points away from this root. This gives the baseline cost.
Next, perform a second DFS to reroot the tree. When moving the root from u to its neighbor v, the orientation of that edge flips relative to the root. If the edge originally required a toggle, the new root reduces the total by one; otherwise it increases by one. Propagate this adjustment while traversing the tree. Each node’s value represents the total toggles required if that node were the root.
This rerooting pattern appears frequently in tree and graph problems. The key insight is that neighboring roots differ by only one edge’s contribution, so you update the cost in constant time per transition. The full traversal touches each edge twice, giving O(n) time and O(n) memory for adjacency storage.
Recommended for interviews: The rerooting DFS solution is what interviewers expect. Starting with the brute force approach shows you understand how edge orientation affects the count. Moving to rerooting demonstrates strong knowledge of Depth-First Search patterns and tree DP optimizations.
We define an adjacency list g to represent the tree, where g[a] stores all adjacent nodes of node a and the indices of the corresponding edges.
We design a function dfs(a, fa), which indicates whether the edge between node a and fa needs to be toggled in the subtree rooted at node a with parent fa. The logic of the function dfs(a, fa) is as follows:
rev, indicating whether node a needs to be toggled. The initial value is start[a] \ne target[a].b of node a and the corresponding edge index i:b \ne fa, recursively call dfs(b, a).[a, b] in the subtree needs to be toggled. We add the edge index i to the answer list and toggle rev.rev.Finally, we call dfs(0, -1). If the return value is true, it means it is impossible to convert start to target, so we return [-1]. Otherwise, we sort the answer list and return it.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of nodes in the tree.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force: DFS from Every Root | O(n^2) | O(n) | Useful for understanding the cost calculation or when n is very small |
| DFS with Rerooting | O(n) | O(n) | Optimal approach for large trees; computes answer for all roots efficiently |
Q4. Minimum Edge Toggles on a Tree || Easy DFS Approach || Leetcode Biweekly Contest 174 || Watch2X🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 526 views views
Watch 3 more video solutions →Practice Minimum Edge Toggles on a Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor