Skip to main content
Talentd

Minimum Edge Toggles on a Tree - Solution & Explanation

HardTreeDepth-First SearchGraphTopological Sort12 min read
Practice this problem

Problem Statement

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:

  • Toggle edge with index 1, which flips nodes 1 and 2.
  • Toggle edge with index 2, which flips nodes 2 and 3.
  • Toggle edge with index 5, which flips nodes 1 and 6.

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 <= 105
  • edges.length == n - 1
  • edges[i] = [ai, bi]
  • 0 <= ai, bi < n
  • start[i] is either '0' or '1'.
  • target[i] is either '0' or '1'.
  • The input is generated such that edges represents a valid tree.

Approach Overview

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.

Solution

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:

  1. Initialize a boolean variable rev, indicating whether node a needs to be toggled. The initial value is start[a] \ne target[a].
  2. Iterate through all adjacent nodes b of node a and the corresponding edge index i:
    • If b \ne fa, recursively call dfs(b, a).
    • If the recursive call returns true, it means the edge [a, b] in the subtree needs to be toggled. We add the edge index i to the answer list and toggle rev.
  3. Return 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force: DFS from Every RootO(n^2)O(n)Useful for understanding the cost calculation or when n is very small
DFS with RerootingO(n)O(n)Optimal approach for large trees; computes answer for all roots efficiently

Video Solution

Q4. Minimum Edge Toggles on a Tree || Easy DFS Approach || Leetcode Biweekly Contest 174 || Watch2X🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 617 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Minimum Edge Toggles on a Tree easy or hard?
Minimum Edge Toggles on a Tree is classified as Hard because it requires recognizing a rerooting dynamic programming pattern on trees. The brute-force idea is simple, but optimizing it to O(n) with two DFS passes and careful edge contribution updates is the main challenge.
Minimum Edge Toggles on a Tree Python/Java solution
Implement the algorithm using an adjacency list and two DFS traversals. The first DFS calculates the number of edges that must be toggled for an initial root. The second DFS performs rerooting and updates the cost for each neighbor by adjusting the toggle count based on the edge orientation. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Minimum Edge Toggles on a Tree in O(n)?
Build an adjacency list that records whether traversing an edge matches the desired direction. Run a DFS from an initial root to count the number of edges that require toggling. Then perform a second DFS to reroot: moving the root across an edge changes the total cost by ±1 depending on that edge’s orientation. Propagating this adjustment computes the answer for all nodes in linear time.
What is the best approach for Minimum Edge Toggles on a Tree?
The most efficient approach uses DFS with a rerooting technique. First compute the number of incorrect edge orientations assuming an arbitrary root, then propagate results to neighboring nodes by adjusting the cost when the root moves. This processes each edge a constant number of times, giving O(n) time complexity.
Is Minimum Edge Toggles on a Tree asked at Google/Amazon/Meta?
Tree rerooting and edge orientation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include counting edge reversals, reorienting routes in a tree, or computing costs for every possible root using DFS dynamic programming.
What data structure is used in Minimum Edge Toggles on a Tree?
The core data structure is an adjacency list representing the tree. Each entry stores the neighboring node and metadata about whether the edge direction matches or conflicts with the desired orientation. DFS traversal and rerooting logic operate directly on this structure.
What is the time complexity of Minimum Edge Toggles on a Tree?
The optimal DFS rerooting solution runs in O(n) time where n is the number of nodes in the tree. Each edge is processed during the initial DFS and once again during the reroot traversal. Space complexity is O(n) due to the adjacency list and recursion stack.

Ready to solve this problem?

Practice Minimum Edge Toggles on a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II