3812. Minimum Edge Toggles on a Tree

HardTreeDepth-First SearchGraphTopological SortSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an undirected tree with n nodes, numbered from 0 to n - 1. The tree is represented by a 2D integer array edges of length n - 1, where edges[i] = [aᵢ, bᵢ] means there is an edge connecting nodes aᵢ and bᵢ.

You are also given two binary strings start and target, each of length n. For every node x:

start[x] represents the initial color of node x (either '0' or '1').
target[x] represents the desired color of node x (either '0' or '1').

In one operation, you choose an edge with index i, say [u, v], and toggle both of its endpoints. Toggling means flipping the color of a node from '0' to '1' or from '1' to '0'. Note that both endpoints u and v are flipped at the same time.

Your goal is to find a sequence of edge operations that transforms the start configuration into the target configuration. Among all valid sequences that have the minimum possible length, return the chosen edge indices in increasing order.

If it is impossible to transform start into target, return an array containing a single element equal to -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why DFS?

This problem maps to DFS through a short path in the full flowchart.

Recursively exploring the tree depth-first processes each subtree naturally.

Open in Flowchart

Show step-by-step reasoning

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: The problem explicitly involves nodes (numbered 0 to n - 1) connected by edges, forming an undirected structure.

Is it a tree?

Yes: The problem states we are given an undirected tree with n nodes and n - 1 edges, which is the defining property of a tree.

Conclusion: The flowchart leads us directly to the DFS pattern. Since the structure is a tree, we can root it at node 0 and use Depth-First Search to traverse it. At each node, we determine whether its color matches the target. By processing children first and propagating the toggle requirement back up to the parent edge, DFS lets us greedily decide which edges must be toggled — yielding the minimum set of operations that transform start into target.

Intuition

The key observation is that each operation toggles both endpoints of an edge. So whether a node ends up with the correct color depends on how many times the edges touching it are toggled — specifically, on the parity (odd or even count) of those toggles.

Let's think about what each edge "does." If we focus on any single edge and decide whether to use it (toggle it an odd number of times) or not (toggle it an even number of times), then using an edge twice is wasteful — it cancels out. So in the minimum-length sequence, every edge is used at most once. This means our real decision is just a yes/no choice for each edge: toggle it or not.

Now, since the graph is a tree, there is a beautiful structure we can exploit. Root the tree at node 0. Consider any node a and the edge connecting it to its parent. That edge is the only edge that can fix node a's color without disturbing nodes outside a's subtree. Every other edge touching a connects it to a child, and toggling those edges is decided while we handle the children.

This leads to a natural bottom-up strategy using DFS:

For a node a, first recursively resolve all of its children's subtrees.
When a child reports that the edge between a and that child needs to be toggled, we apply it. This also flips node a as a side effect, so we track that.
After processing all children, we check whether node a still needs fixing. A node needs fixing when start[a] != target[a], combined with all the flips it already received from child edges.
If node a still doesn't match its target, the only remaining way to fix it is through the edge to its parent — so we report back to the parent that this edge must be toggled.

We represent this "needs to be toggled" signal as the boolean return value rev of the DFS. It is computed as start[a] != target[a], then flipped once for each child edge we decided to use.

Finally, the root node 0 has no parent. So if the DFS at the root returns true — meaning the root still needs fixing but has no parent edge to do it — the transformation is impossible, and we return [-1]. Otherwise, the collected edge indices form the minimum-length answer, which we sort in increasing order before returning.

Pattern Learn more about Tree, Depth-First Search, Graph, Topological Sort and Sorting patterns.

Solution Approach

We use a DFS traversal over the tree to decide, for each edge, whether it must be toggled. The implementation relies on an adjacency list to store the tree and a single recursive function that returns whether a node still needs fixing.

Step 1: Build the adjacency list.

We define an adjacency list g, where g[a] stores all adjacent nodes of node a together with the index of the corresponding edge. For each edge edges[i] = [a, b], we add (b, i) to g[a] and (a, i) to g[b], so we can later recover which edge index connects two nodes.

g = [[] for _ in range(n)]
for i, (a, b) in enumerate(edges):
    g[a].append((b, i))
    g[b].append((a, i))

Step 2: Design the DFS function.

We design a function dfs(a, fa), where a is the current node and fa is its parent. The return value tells the parent whether the edge between a and fa needs to be toggled. The logic is:

Initialize a boolean variable rev indicating whether node a currently needs to be toggled. Its initial value is start[a] != target[a].
Iterate through all adjacent nodes b of node a and the corresponding edge index i:
- If b != fa, recursively call dfs(b, a).
- If the recursive call returns true, the edge [a, b] must be toggled. We append the edge index i to the answer list ans and flip rev (since toggling this edge also flips node a).
Return rev.

def dfs(a: int, fa: int) -> bool:
    rev = start[a] != target[a]
    for b, i in g[a]:
        if b != fa and dfs(b, a):
            ans.append(i)
            rev = not rev
    return rev

Step 3: Run the DFS and produce the answer.

We call dfs(0, -1), rooting the tree at node 0 with a sentinel parent -1. If the return value is true, it means the root still needs fixing but has no parent edge to do it, so the transformation is impossible and we return [-1]. Otherwise, we sort the collected edge indices in increasing order and return them.

if dfs(0, -1):
    return [-1]
ans.sort()
return ans

Complexity Analysis:

Time complexity: O(n log n). The DFS visits each node and edge once in O(n), and sorting the answer list takes O(n log n).
Space complexity: O(n). The adjacency list, recursion stack, and answer list each use O(n) space.

Example Walkthrough

Let's trace through a concrete example to see the bottom-up DFS in action.

Input:

n = 4
edges = [[0, 1], [1, 2], [1, 3]]
start = "1100"
target = "0011"

So the tree looks like this (rooted at node 0):

        0          start[0]=1, target[0]=0  → mismatch
        |  (edge 0)
        1          start[1]=1, target[1]=0  → mismatch
       / \
(edge 1)  (edge 2)
     /       \
    2         3      start[2]=0, target[2]=1 → mismatch
                     start[3]=0, target[3]=1 → mismatch

Every node currently mismatches its target, so rev starts as true for all four nodes.

Step 1: Build the adjacency list.

g[0] = [(1, 0)]
g[1] = [(0, 0), (2, 1), (3, 2)]
g[2] = [(1, 1)]
g[3] = [(1, 2)]

Step 2: Run dfs(0, -1). We process the tree bottom-up.

→ Visit node 0, call dfs(0, -1).

rev = (start[0] != target[0]) = (1 != 0) = true.
Neighbor (1, 0): 1 != -1, so recurse into dfs(1, 0).

→ Visit node 1, call dfs(1, 0). - rev = (1 != 0) = true. - Neighbor (0, 0): equals parent fa=0, skip. - Neighbor (2, 1): recurse into dfs(2, 1).

→ Visit node 2 (leaf), call dfs(2, 1). - rev = (0 != 1) = true. No non-parent neighbors. - Returns true → node 2 must be fixed via its parent edge (edge 1).

- Back in node 1: child returned true, so append edge 1 → ans = [1], and flip rev: true → false. (Toggling edge 1 fixes node 2 and also flips node 1.) - Neighbor (3, 2): recurse into dfs(3, 1).

→ Visit node 3 (leaf), call dfs(3, 1). - rev = (0 != 1) = true. No non-parent neighbors. - Returns true → node 3 must be fixed via its parent edge (edge 2).

- Back in node 1: child returned true, so append edge 2 → ans = [1, 2], and flip rev: false → true. - Done with children. Node 1 returns rev = true → node 1 still needs fixing via its parent edge (edge 0).

Back in node 0: child returned true, so append edge 0 → ans = [1, 2, 0], and flip rev: true → false.
Done with children. Node 0 returns rev = false.

Step 3: Produce the answer.

dfs(0, -1) returned false, so the transformation is possible. Sort ans = [1, 2, 0] in increasing order:

ans = [0, 1, 2]

Verification. Apply the toggles to start = "1100":

Edge toggled	Endpoints flipped	Configuration
—	—	`1100`
edge 0 → `[0,1]`	nodes 0, 1	`0000`
edge 1 → `[1,2]`	nodes 1, 2	`0110`
edge 2 → `[1,3]`	nodes 1, 3	`0011`

The final configuration 0011 matches target exactly. ✅

Why this is minimal: Each edge was used at most once (using it twice would cancel out), and every edge we chose was forced — it was the only edge able to fix a node's subtree without disturbing already-resolved nodes. Hence [0, 1, 2] is a minimum-length solution.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minimumFlips(
6        self, n: int, edges: List[List[int]], start: str, target: str
7    ) -> List[int]:
8        # Build adjacency list: each entry stores (neighbor, edge_index)
9        graph = [[] for _ in range(n)]
10        for edge_index, (node_a, node_b) in enumerate(edges):
11            graph[node_a].append((node_b, edge_index))
12            graph[node_b].append((node_a, edge_index))
13
14        # Stores the indices of edges that must be flipped
15        flipped_edges = []
16
17        def dfs(node: int, parent: int) -> bool:
18            # Whether this node currently mismatches its target,
19            # i.e. it still needs a flip to be resolved.
20            needs_flip = start[node] != target[node]
21            for neighbor, edge_index in graph[node]:
22                # Skip the edge leading back to the parent
23                if neighbor != parent and dfs(neighbor, node):
24                    # The child's subtree still needs a flip,
25                    # so flip the edge connecting child to current node.
26                    flipped_edges.append(edge_index)
27                    # Flipping this edge toggles the current node's state.
28                    needs_flip = not needs_flip
29            return needs_flip
30
31        # If after processing the whole tree the root still needs a flip,
32        # there is no valid set of flips to reach the target.
33        if dfs(0, -1):
34            return [-1]
35
36        # Return the edge indices in ascending order
37        flipped_edges.sort()
38        return flipped_edges
39

1class Solution {
2    // Stores the indices of edges that must be flipped
3    private final List<Integer> answer = new ArrayList<>();
4    // Adjacency list: each entry holds {neighborNode, edgeIndex}
5    private List<int[]>[] graph;
6    // Character arrays for the starting and target binary states
7    private char[] startState;
8    private char[] targetState;
9
10    public List<Integer> minimumFlips(int n, int[][] edges, String start, String target) {
11        // Initialize the adjacency list for all n nodes
12        graph = new List[n];
13        Arrays.setAll(graph, k -> new ArrayList<>());
14
15        // Build the undirected tree; record each edge's original index
16        for (int i = 0; i < n - 1; ++i) {
17            int nodeA = edges[i][0], nodeB = edges[i][1];
18            graph[nodeA].add(new int[] {nodeB, i});
19            graph[nodeB].add(new int[] {nodeA, i});
20        }
21
22        // Convert the input strings to char arrays for fast comparison
23        this.startState = start.toCharArray();
24        this.targetState = target.toCharArray();
25
26        // Run DFS from the root (node 0). If the root itself still needs
27        // a flip but has no parent edge to flip, the task is impossible.
28        if (dfs(0, -1)) {
29            return List.of(-1);
30        }
31
32        // Return the required edge indices in ascending order
33        Collections.sort(answer);
34        return answer;
35    }
36
37    /**
38     * Performs a post-order DFS to decide which edges must be flipped.
39     *
40     * @param current the current node being processed
41     * @param parent  the node we came from (to avoid revisiting)
42     * @return true if the edge connecting {@code current} to its parent
43     *         must be flipped so that {@code current} matches its target
44     */
45    private boolean dfs(int current, int parent) {
46        // Initially, this node needs a flip if its value differs from the target
47        boolean needFlip = startState[current] != targetState[current];
48
49        // Visit all neighbors except the parent
50        for (var edge : graph[current]) {
51            int neighbor = edge[0], edgeIndex = edge[1];
52            if (neighbor != parent && dfs(neighbor, current)) {
53                // The child requires its parent edge (this edge) to be flipped
54                answer.add(edgeIndex);
55                // Flipping this edge also toggles the current node's effective value
56                needFlip = !needFlip;
57            }
58        }
59
60        // Propagate whether the current node still needs its parent edge flipped
61        return needFlip;
62    }
63}
64

1class Solution {
2public:
3    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
4        // Build adjacency list: each entry stores {neighbor, edgeIndex}
5        vector<vector<pair<int, int>>> graph(n);
6        for (int i = 0; i < n - 1; ++i) {
7            int from = edges[i][0], to = edges[i][1];
8            graph[from].push_back({to, i});
9            graph[to].push_back({from, i});
10        }
11
12        vector<int> answer; // Stores indices of edges that need flipping
13
14        // DFS returns true if node `cur` still needs an additional flip
15        // that must be resolved by flipping the edge to its parent.
16        auto dfs = [&](this auto&& dfs, int cur, int parent) -> bool {
17            // A node needs a flip if its start value differs from its target.
18            bool needFlip = start[cur] != target[cur];
19
20            // Process all children
21            for (auto [next, edgeIdx] : graph[cur]) {
22                // Skip the edge leading back to the parent
23                if (next != parent && dfs(next, cur)) {
24                    // The child still needs a flip, so flip the edge between
25                    // `cur` and `next`. This also toggles `cur`'s state.
26                    answer.push_back(edgeIdx);
27                    needFlip = !needFlip;
28                }
29            }
30
31            // Report upward whether this node still requires a flip.
32            return needFlip;
33        };
34
35        // If the root still needs a flip, there is no edge above it to fix it,
36        // so the configuration is impossible.
37        if (dfs(0, -1)) {
38            return {-1};
39        }
40
41        // Return edge indices in sorted order.
42        ranges::sort(answer);
43        return answer;
44    }
45};
46

1/**
2 * Determines the set of edges to flip so that every node's value
3 * transitions from `start` to `target`.
4 *
5 * The tree is processed with a post-order DFS. For each node, `needsFlip`
6 * tracks whether its value currently mismatches the target after applying
7 * flips propagated up from its children. An edge to a child is flipped when
8 * that child's subtree reports a pending mismatch.
9 *
10 * @param n      Number of nodes in the tree.
11 * @param edges  List of [a, b] pairs describing tree edges (length n - 1).
12 * @param start  Initial binary string of node values.
13 * @param target Desired binary string of node values.
14 * @returns      Sorted indices of edges to flip, or [-1] if impossible.
15 */
16function minimumFlips(
17    n: number,
18    edges: number[][],
19    start: string,
20    target: string,
21): number[] {
22    // Adjacency list: graph[node] = array of [neighbor, edgeIndex].
23    const graph: number[][][] = Array.from({ length: n }, () => []);
24    for (let i = 0; i < n - 1; i++) {
25        const [a, b] = edges[i];
26        graph[a].push([b, i]);
27        graph[b].push([a, i]);
28    }
29
30    // Collected indices of edges that must be flipped.
31    const answer: number[] = [];
32
33    /**
34     * Post-order DFS over the tree.
35     *
36     * @param node   Current node being visited.
37     * @param parent Parent node (or -1 for the root).
38     * @returns      Whether this node still mismatches the target after
39     *               processing its children (a pending flip to propagate up).
40     */
41    const dfs = (node: number, parent: number): boolean => {
42        // True if the current node's value differs from its target value.
43        let needsFlip = start[node] !== target[node];
44
45        for (const [next, edgeIndex] of graph[node]) {
46            // Skip the edge leading back to the parent.
47            if (next !== parent && dfs(next, node)) {
48                // The child reported a mismatch: flip the connecting edge,
49                // which also toggles the current node's pending state.
50                answer.push(edgeIndex);
51                needsFlip = !needsFlip;
52            }
53        }
54
55        return needsFlip;
56    };
57
58    // If the root still mismatches after processing, no solution exists.
59    if (dfs(0, -1)) {
60        return [-1];
61    }
62
63    // Return edge indices in ascending order.
64    answer.sort((x, y) => x - y);
65    return answer;
66}
67

Time and Space Complexity

Time Complexity

The time complexity is O(n × log n). The analysis is as follows:

Building the adjacency list: The tree has n nodes and n - 1 edges. Iterating over all edges to construct the graph g takes O(n) time.
The DFS traversal: The function dfs visits each node exactly once, and at each node it iterates over its neighbors. Since the total number of edges in the adjacency list is 2 × (n - 1), the entire traversal processes each edge a constant number of times, costing O(n) overall. The boolean operations and the ans.append(i) at each visited node are O(1).
Sorting the answer: The list ans can contain up to O(n) edge indices. Sorting it with ans.sort() takes O(n × log n) time.

Combining these, the overall time complexity is dominated by the sorting step, giving O(n) + O(n × log n) = O(n × log n). Here, n is the number of nodes in the tree.

Space Complexity

The space complexity is O(n). The analysis is as follows:

Adjacency list g: Storing the graph requires O(n) space, since there are n nodes and 2 × (n - 1) directed edge entries.
Answer list ans: In the worst case it holds up to O(n) edge indices.
Recursion stack: The depth of the dfs recursion can reach O(n) in a degenerate (chain-like) tree.

Summing these contributions yields a total space complexity of O(n), where n is the number of nodes in the tree.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Recursion Depth Limit Exceeded on Deep Trees

The most common pitfall with this DFS-based solution is hitting Python's default recursion limit (typically 1000). A tree with n nodes can degenerate into a "chain" (e.g., 0 - 1 - 2 - ... - (n-1)), which forces a recursion depth proportional to n. For large inputs (e.g., n = 10^5), the recursive dfs will throw a RecursionError before it ever completes.

Why it happens: The recursion depth equals the height of the tree. A balanced tree has height O(log n), but a skewed/linear tree has height O(n), which easily blows past the default limit.

Solution A — Raise the recursion limit:

import sys

class Solution:
    def minimumFlips(self, n, edges, start, target):
        sys.setrecursionlimit(n + 10)  # add headroom for the call frame overhead
        # ... rest of the recursive solution unchanged

This is a quick fix, but be aware that very deep recursion may still risk a C-level stack overflow (segfault) on some systems even after raising the limit.

Solution B — Convert to an explicit iterative DFS (most robust):

The cleaner fix uses an explicit stack. The trick is to process a node after all its children are done (post-order), since the parent needs the children's return values. We use a two-pass marker approach:

class Solution:
    def minimumFlips(self, n, edges, start, target):
        graph = [[] for _ in range(n)]
        for edge_index, (a, b) in enumerate(edges):
            graph[a].append((b, edge_index))
            graph[b].append((a, edge_index))

        flipped_edges = []
        needs_flip = [start[i] != target[i] for i in range(n)]
        parent = [-1] * n
        parent_edge = [-1] * n

        # Iterative post-order traversal
        stack = [(0, -1, False)]
        while stack:
            node, par, processed = stack.pop()
            if processed:
                # All children have been resolved; finalize this node.
                if needs_flip[node] and par != -1:
                    flipped_edges.append(parent_edge[node])
                    needs_flip[par] = not needs_flip[par]
            else:
                stack.append((node, par, True))  # revisit after children
                for neighbor, edge_index in graph[node]:
                    if neighbor != par:
                        parent[neighbor] = node
                        parent_edge[neighbor] = edge_index
                        stack.append((neighbor, node, False))

        if needs_flip[0]:
            return [-1]
        flipped_edges.sort()
        return flipped_edges

This avoids any recursion-depth concern entirely and is the safest choice for large constraints.

Pitfall 2: Returning Unsorted Edge Indices

The DFS appends edge indices in post-order traversal order, not in numeric order. A natural mistake is to return flipped_edges directly, assuming the traversal order matches the required increasing order. It does not.

Why it happens: Edges are appended as subtrees finish processing, which depends on the tree's structure and the adjacency-list ordering — completely unrelated to edge indices.

Solution: Always sort before returning, as the original code correctly does:

flipped_edges.sort()
return flipped_edges

Forgetting the .sort() call will produce a set with the correct elements but in the wrong order, failing exact-match validation.

Pitfall 3: Misidentifying the Parent When the Tree Has Duplicate-Looking Neighbors

The condition if neighbor != parent correctly skips the edge back to the parent in a tree (no cycles, no parallel edges). However, a subtle danger arises if you mistakenly track the parent node instead of the parent edge in graphs that could (hypothetically) contain multiple edges between the same pair of nodes.

Why it matters here: The problem guarantees a tree, so neighbor != parent is safe. But if you reuse this pattern on a general graph or a multigraph, comparing node identity alone may incorrectly skip a legitimate edge or fail to skip the true back-edge.

Solution: For a tree, the current approach is correct. For safety in more general settings, skip based on the edge index used to arrive at the node rather than the parent node identity:

def dfs(node, incoming_edge):
    needs_flip = start[node] != target[node]
    for neighbor, edge_index in graph[node]:
        if edge_index != incoming_edge and dfs(neighbor, edge_index):
            flipped_edges.append(edge_index)
            needs_flip = not needs_flip
    return needs_flip
# Initial call: dfs(0, -1)

This makes the traversal robust regardless of how the parent relationship is structured.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering