Loading…

mediumGraphsSometimes asked

Even Tree

Q: How do you solve Even Tree using the Recursive DFS Subtree Sizes (Baseline) approach?

When to use it: The clearest way to state the idea: a post-order recursion returns each subtree's size, and you count even ones along the way. Then flag the recursion-depth caveat for large trees. Subtree sizes are the whole game, and a post-order DFS computes them in one sweep. **Why subtree size decides each edge.** In a rooted tree, the only edge that isolates node `u`'s subtree from everything else is the edge from `u` to its parent. Cutting it produces a component that is exactly `u`'s subtree. So that cut is legal — yields an even component — precisely when `size[u]` is even. **Why the greedy is also maximal.** Suppose you cut the parent edges of every non-root node with an even subtree. Each such cut removes an even-sized piece, and because `N` is even, the part left behind after removing an even piece is still even. So no cut spoils another's validity, and every legal cut can be taken simultaneously. You cannot do better than cutting *every* legal edge, so counting them is optimal. **Why the root is excluded.** The root has no parent, hence no edge above it to cut. Its subtree (the whole tree, size `N`, which is even) is never a separable piece, so it must not be counted. **The recursion shape.** `dfs(u, parent)` returns `size(u)`: start at 1, add `dfs(child, u)` for each neighbor that is not the parent, and if the returned size is even and `u` is not the root, bump the counter. Skipping the parent is how an undirected edge list is treated as a rooted tree without a separate visited array. **The caveat.** On a skewed tree (a long chain), the recursion nests `O(V)` deep. With small `N` here that is safe, but as a habit you should note that a deep tree can overflow the call stack — which motivates the iterative version. Time complexity: O(V). Space complexity: O(V) recursion stack.

Q: How do you solve Even Tree using the Iterative DFS Subtree Sizes (Optimal) approach?

When to use it: The production-safe version. Compute a traversal order with an explicit stack, then accumulate sizes in reverse — no recursion, so no stack-overflow risk on a deep tree. The logic is identical to the recursion; only the mechanism changes so a deep tree cannot blow the call stack. **Step 1 — order and parents.** Run an iterative DFS (or BFS) from the root using an explicit stack. When you pop a node, append it to an `order` list and push each neighbor that is not its parent, recording the parent as you go. Because the tree is acyclic, each node is pushed exactly once; the parent check replaces a visited array. In the resulting `order`, every node appears *before* all of its descendants. **Step 2 — sizes in reverse.** Initialize `size[u] = 1` for all nodes. Iterate `order` in reverse. When you reach node `u`, all of its descendants have already been processed, so `size[u]` has already accumulated every child's subtree — it is final. If `u` is not the root and `size[u]` is even, increment the cut count. Then fold `u`'s size into its parent: `size[parent[u]] += size[u]`. By the time you reach any node, its full subtree size is known, exactly mirroring post-order recursion. **Why this is the safe default.** The only difference from the recursive version is that the deferral lives on an explicit heap-allocated stack and an array sweep, not on the call stack. A chain of `10⁵` nodes — or any skewed tree — processes without risk of overflow. The time and the answer are identical. **Why the parity rule is unchanged.** Cutting the parent edge of an even subtree still peels off an even component and leaves an even remainder (N is even), so every even non-root subtree is an independent, valid, and necessary cut. The count is the maximum number of removable edges. Time complexity: O(V). Space complexity: O(V).

Graphs · 24 of 34 · 11 min

You are given a tree (a connected, acyclic, undirected graph) of N nodes labeled 1 to N, rooted at node 1, described by a list of edges. N is even.

Remove as many edges as possible so that every resulting connected component has an even number of nodes. Return the maximum number of edges you can remove.

In plain English

Rooting the tree at node 1 gives every node (except the root) exactly one parent edge — the only edge you could cut to separate that node's subtree from the rest. Cutting it carves off a component equal to that subtree. For the carved-off piece to be even, the subtree must have an even node count; and because the whole tree has an even count, whatever remains after removing an even piece is also even. So each even subtree is an independently safe cut, and the answer is how many such subtrees exist below the root.

Examples

Example 1

Input: N = 10, edges = [[2,1],[3,1],[4,3],[5,2],[6,1],[7,2],[8,6],[9,8],[10,8]]
Output: 2
Note: Subtree of 3 = {3,4} (size 2) and subtree of 6 = {6,8,9,10} (size 4) are even. Cutting both leaves {1,2,5,7} (size 4). All even → 2 edges removed.

Example 2

Input: N = 4, edges = [[1,2],[2,3],[3,4]]
Output: 1
Note: Only node 3 has an even subtree {3,4} (size 2). Cut edge 2–3 → {3,4} and {1,2}, both even. 1 edge.

Example 3

Input: N = 4, edges = [[1,2],[1,3],[1,4]]
Output: 0
Note: Each leaf's subtree has size 1 (odd). No even non-root subtree exists, so no edge can be cut.

Constraints

2 ≤ N ≤ 100 (and N is even)
The graph is a tree: exactly N − 1 edges, connected, acyclic
Nodes are labeled 1 to N, rooted at node 1
Edges are undirected; build the tree by skipping the parent when recursing
A valid partition always exists because N is even

Clarifying questions4First question: Is N guaranteed even?Explore questions

Q1.Is N guaranteed even?
Yes. If N were odd, no partition into all-even components could exist (the sizes would have to sum to an odd total). Evenness of N is what guarantees a solution.
Q2.Is the input really a tree?
Yes — connected and acyclic with N − 1 edges. That is why every non-root node has a unique parent edge and well-defined subtree.
Q3.Can cutting one edge make another cut invalid?
No. Removing an even subtree leaves an even remainder, so other even subtrees stay even. The cuts are independent — that is the heart of the greedy.
Q4.Does the root's subtree count?
No. The root has no parent edge, so its (size N) subtree can never be detached. Only non-root even subtrees count.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Root the tree and compute every node's subtree size with a single DFS. You may cut the edge above any non-root node whose subtree has an even number of nodes — doing so peels off an even component and leaves the rest even too. The maximum number of removable edges is simply the count of non-root nodes with an even subtree size. O(V).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you root the tree, see that a single DFS subtree-size pass suffices, and can argue why cutting every even subtree is both valid and maximal — plus whether you make the traversal iterative for large trees.

Where candidates slip

Counting the root's subtree (it has no parent edge to cut), assuming cuts conflict and reaching for DP, or recursing and overflowing the stack on a skewed tree.

How to stand out

Prove the greedy: cutting an even subtree leaves an even remainder because N is even, so the cuts never interfere. Then note the answer is a plain count of even non-root subtrees, computed in O(V).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive DFS Subtree Sizes (Baseline)	`O(V)`	`O(V) recursion stack`	The clearest way to state the idea: a post-order recursion returns each subtree's size, and you count even ones along the way. Then flag the recursion-depth caveat for large trees.	Read
2	Iterative DFS Subtree Sizes (Optimal)Optimal	`O(V)`	`O(V)`	The production-safe version. Compute a traversal order with an explicit stack, then accumulate sizes in reverse — no recursion, so no stack-overflow risk on a deep tree.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewNode u (not root)size[u] even?YesNoExplore the full tree

Even subtrees that can be detached

How to read it:Subtrees {3,4} (size 2) and {6,8,9,10} (size 4) are even; cutting their parent edges leaves {1,2,5,7} (size 4).

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive DFS Subtree Sizes (Baseline)

TimeO(V)SpaceO(V) recursion stack

The clearest way to state the idea: a post-order recursion returns each subtree's size, and you count even ones along the way. Then flag the recursion-depth caveat for large trees.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Root the tree at node 1. What single number per node tells you whether its parent edge is cuttable?

2Hint 2Explore hint

A subtree's size is 1 plus the sizes of its children's subtrees — a textbook post-order recursion.

3Hint 3Explore hint

While returning each size, if it is even and the node is not the root, increment a cut counter.

A · Core idea

Subtree sizes are the whole game, and a post-order DFS computes them in one sweep.

Why subtree size decides each edge. In a rooted tree, the only edge that isolates node u's subtree from everything else is the edge from u to its parent. Cutting it produces a component that is exactly u's subtree. So that cut is legal — yields an even component — precisely when size[u] is even.

Why the greedy is also maximal. Suppose you cut the parent edges of every non-root node with an even subtree. Each such cut removes an even-sized piece, and because N is even, the part left behind after removing an even piece is still even. So no cut spoils another's validity, and every legal cut can be taken simultaneously. You cannot do better than cutting every legal edge, so counting them is optimal.

Why the root is excluded. The root has no parent, hence no edge above it to cut. Its subtree (the whole tree, size N, which is even) is never a separable piece, so it must not be counted.

The recursion shape. dfs(u, parent) returns size(u): start at 1, add dfs(child, u) for each neighbor that is not the parent, and if the returned size is even and u is not the root, bump the counter. Skipping the parent is how an undirected edge list is treated as a rooted tree without a separate visited array.

The caveat. On a skewed tree (a long chain), the recursion nests O(V) deep. With small N here that is safe, but as a habit you should note that a deep tree can overflow the call stack — which motivates the iterative version.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 4, edges = [[1,2],[2,3],[3,4]]

Interactive diagram

Post-order sizes up a chain

dfs(4)

Active call / nodeSupporting contextReturned stateNot active

Sizes returned bottom-up: 1, 2, 3, 4. Only the size-2 subtree at node 3 is a cut.

Final result1

C · Code with teaching comments

Reference implementation previewprivate List<List<Integer>> adj; private int cuts; public int evenForest(int n, int[][] edges) { adj = new ArrayList<>();Explore the full code

solution.javaJava

Recursive DFS Subtree Sizes (Baseline) — reference

3 teaching notes

1
private List<List<Integer>> adj;
2
private int cuts;
3
 
4
public int evenForest(int n, int[][] edges) {
5
    adj = new ArrayList<>();
6
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
7
    for (int[] e : edges) {
8
        adj.get(e[0]).add(e[1]);
9
        adj.get(e[1]).add(e[0]);
10
    }
11
    cuts = 0;
12
    // Root the tree at node 1; sentinel parent 0 has no real edge.
13
    dfs(1, 0);                       // root at 1, no parent (0)
14
    return cuts;
15
}
16
 
17
private int dfs(int u, int parent) {
18
    int size = 1;
19
    for (int v : adj.get(u)) {
20
        // Treats the undirected edge list as a rooted tree without a visited array.
21
        if (v != parent) {           // skip the edge back to the parent
22
            size += dfs(v, u);
23
        }
24
    }
25
    // Cut the parent edge exactly when the subtree is even and u is not the root.
26
    if (u != 1 && size % 2 == 0) {   // even subtree, not the root → cuttable
27
        cuts++;
28
    }
29
    return size;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(V) timeO(V) recursion stack spaceOpen the invariant and proofExplore the proof

One post-order pass yields every subtree size, and the cut rule is a one-line parity test. The greedy is justified by N being even: removing an even chunk always leaves an even chunk, so the cuts never collide.

ComplexityO(V) time, O(V) recursion stack space — Each node is visited once and its size computed from its children → O(V) time. The recursion stack can be as deep as the tree height, which is O(V) on a skewed (chain) tree.

E · Edge cases and pitfalls3Counting the root's even subtree — it has no parent edge to cut.Explore edge cases

Pitfalls

Counting the root's even subtree — it has no parent edge to cut.
Recursing without a parent guard — infinite loop on the undirected edges.
Deep recursion on a chain — risk of stack overflow; switch to iterative.

03.2

Approach 2 of 2 · Optimal

Iterative DFS Subtree Sizes (Optimal)

TimeO(V)SpaceO(V)

The production-safe version. Compute a traversal order with an explicit stack, then accumulate sizes in reverse — no recursion, so no stack-overflow risk on a deep tree.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The recursion only used the stack to defer a parent until its children finished. Can you get the same post-order effect without the call stack?

2Hint 2Explore hint

Do an iterative DFS from the root recording parents and a visit order. A node always appears before its children in that order.

3Hint 3Explore hint

Walk the order in REVERSE: each node's children are already processed, so its size is final. Count it if even and non-root, then add its size to its parent.

A · Core idea

The logic is identical to the recursion; only the mechanism changes so a deep tree cannot blow the call stack.

Step 1 — order and parents. Run an iterative DFS (or BFS) from the root using an explicit stack. When you pop a node, append it to an order list and push each neighbor that is not its parent, recording the parent as you go. Because the tree is acyclic, each node is pushed exactly once; the parent check replaces a visited array. In the resulting order, every node appears before all of its descendants.

Step 2 — sizes in reverse. Initialize size[u] = 1 for all nodes. Iterate order in reverse. When you reach node u, all of its descendants have already been processed, so size[u] has already accumulated every child's subtree — it is final. If u is not the root and size[u] is even, increment the cut count. Then fold u's size into its parent: size[parent[u]] += size[u]. By the time you reach any node, its full subtree size is known, exactly mirroring post-order recursion.

Why this is the safe default. The only difference from the recursive version is that the deferral lives on an explicit heap-allocated stack and an array sweep, not on the call stack. A chain of 10⁵ nodes — or any skewed tree — processes without risk of overflow. The time and the answer are identical.

Why the parity rule is unchanged. Cutting the parent edge of an even subtree still peels off an even component and leaves an even remainder (N is even), so every even non-root subtree is an independent, valid, and necessary cut. The count is the maximum number of removable edges.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 6, edges = [[1,2],[2,3],[3,4],[4,5],[5,6]]

Array state

init

all sizes 1 (index 1..6)

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Iterative DFS Subtree Sizes (Optimal) — optimal

4 teaching notes

1
public int evenForest(int n, int[][] edges) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
4
    for (int[] e : edges) {
5
        adj.get(e[0]).add(e[1]);
6
        adj.get(e[1]).add(e[0]);
7
    }
8
    int[] parent = new int[n + 1];
9
    int[] order = new int[n];
10
    int idx = 0;
11
    Deque<Integer> stack = new ArrayDeque<>();
12
    stack.push(1);
13
    parent[1] = 0;
14
    // An explicit stack records a DFS order with parents — no recursion depth to
15
    // overflow.
16
    while (!stack.isEmpty()) {            // iterative DFS, no stack overflow
17
        int u = stack.pop();
18
        order[idx++] = u;
19
        for (int v : adj.get(u)) {
20
            if (v != parent[u]) {
21
                parent[v] = u;
22
                stack.push(v);
23
            }
24
        }
25
    }
26
    int[] size = new int[n + 1];
27
    Arrays.fill(size, 1);
28
    int cuts = 0;
29
    // Processing the order backward guarantees children are summed before their parent.
30
    for (int i = n - 1; i >= 0; i--) {    // reverse order = post-order
31
        int u = order[i];
32
        // Even, non-root subtree → its parent edge is a valid cut.
33
        if (u != 1 && size[u] % 2 == 0) cuts++;
34
        // Fold the finished subtree size up into the parent; the root's parent is the
35
        // unused index 0.
36
        size[parent[u]] += size[u];       // parent[1]=0 → size[0], harmless
37
    }
38
    return cuts;
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(V) timeO(V) spaceOpen the invariant and proofExplore the proof

Recording a DFS order and accumulating sizes in reverse reproduces post-order without recursion. It is the same O(V) computation, made stack-safe — the pattern to reach for whenever a tree might be deep.

ComplexityO(V) time, O(V) space — The forward DFS pushes and pops each node once → O(V). The reverse accumulation visits each node once → O(V). Arrays for parent, size, and the order list are O(V). No recursion stack.

E · Edge cases and pitfalls7N = 2, edges = [[1,2]] — size[2] = 1 (odd) → no cut. A two-node tree is already one even component; answer 0.Explore edge cases

Edge cases handled

N = 2, edges = [[1,2]]size[2] = 1 (odd) → no cut. A two-node tree is already one even component; answer 0.
star: one center, N−1 leavesEvery leaf subtree is size 1 (odd) → 0 cuts unless a leaf chain makes an even subtree.
deep chain of N nodesIterative DFS handles the O(N) depth with no overflow; recursion might not.

Pitfalls

Counting the root (index 1) — exclude it explicitly.
Processing the order forward instead of reversed — parents summed before children, wrong sizes.
Forgetting the parent guard while building the order — would revisit via the undirected edge.
Recursive DFS on a long chain — overflow; the explicit stack avoids it.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int evenForest(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public int evenForest(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] parent = new int[n + 1];
    int[] order = new int[n];
    int idx = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(1);
    parent[1] = 0;
    while (!stack.isEmpty()) {            // iterative DFS, no stack overflow
        int u = stack.pop();
        order[idx++] = u;
        for (int v : adj.get(u)) {
            if (v != parent[u]) {
                parent[v] = u;
                stack.push(v);
            }
        }
    }
    int[] size = new int[n + 1];
    Arrays.fill(size, 1);
    int cuts = 0;
    for (int i = n - 1; i >= 0; i--) {    // reverse order = post-order
        int u = order[i];
        if (u != 1 && size[u] % 2 == 0) cuts++;
        size[parent[u]] += size[u];       // parent[1]=0 → size[0], harmless
    }
    return cuts;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting the root

The root has no parent edge, so its subtree (the whole tree, size N) can never be separated. Including it overcounts by one whenever N is even — which it always is here.

Explore the code comparison

Don't write this

if size[u] % 2 == 0:        # also counts the root
    cuts += 1

Write this instead

if u != root and size[u] % 2 == 0:
    cuts += 1

Missing the parent guard

The edges are undirected, so adj[u] includes the parent. Without skipping it, the traversal walks back up and revisits nodes, corrupting subtree sizes (or looping forever).

Explore the code comparison

Don't write this

for (int v : adj.get(u)) {
    size += dfs(v, u);        // recurses back into the parent
}

Write this instead

for (int v : adj.get(u)) {
    if (v != parent) {        // only descend into children
        size += dfs(v, u);
    }
}

Deep recursion overflow

A skewed tree (a chain) has height equal to N. A recursive DFS nests N call frames and can overflow the stack; an explicit-stack iterative DFS keeps that depth on the heap.

Explore the code comparison

Don't write this

def dfs(u, parent):
    size = 1
    for v in adj[u]:
        if v != parent:
            size += dfs(v, u)   # depth = tree height
    return size

Write this instead

stack = [1]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if v != parent[u]:
            parent[v] = u
            stack.append(v)
# accumulate sizes over reversed(order)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Root the tree, DFS subtree sizes, count even non-root subtrees

Code pattern to memorize

root at 1, compute size[u] = 1 + sum(size[child])
answer = number of nodes u (u != root) with size[u] even
# total nodes N is even, so the leftover is always even too

Rules to remember

1The total node count N is even (guaranteed) — that is what makes an all-even partition possible.
2You may cut the parent edge of node u exactly when size[u] is even; count every such non-root node.
3The root has no parent edge, so it never contributes a cut even if size[root] = N is even.
4Cuts are independent: removing one even subtree leaves both pieces even, so greedily taking all of them is optimal.
5Use an iterative DFS (explicit stack) — a deep or skewed tree can overflow a recursive call stack.

Use this pattern when

Tree problems answerable from **subtree sizes** computed in one post-order pass
Partitioning a tree by cutting edges under a parity / size constraint
Greedy cut decisions that are locally safe and globally independent
Any 'remove edges so each piece satisfies P' on a tree where P depends only on subtree counts

Choose another pattern when

The graph has cycles → it is not a tree; subtree sizes are undefined
Cuts interact (one affects another's validity) → greedy fails, needs DP
You need an actual minimum or weighted partition → tree DP over (cut, not-cut) states
Constraint depends on node values, not counts → size alone is insufficient

Interview takeaway

Subtree sizes from one DFS answer a surprising range of tree questions. Here, an even subtree can always be detached without harming the rest, so the answer is just how many even subtrees hang below the root — a clean greedy backed by the evenness of N.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSubtree-Size DFS with a Greedy Cut Rule. Recognize it when a tree question reduces to a per-node decision based on its subtree count, and the decisions do not interfere. One post-order pass (iterative for safety) yields the sizes; a parity or threshold test yields the answer. The same subtree-size engine powers Diameter, Centroid, and many tree DPs.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Diameter of Binary Tree
Coming soon
Another single post-order pass — combine child heights instead of counting even subtrees.
Tree DP: Maximum Independent Set
Coming soon
When cut decisions interact, move from a greedy count to (include, exclude) tree DP.
Centroid of a Tree
Coming soon
Also driven by subtree sizes — find the node whose removal balances the pieces.
Count of Subtrees With a Given Property
Coming soon
Generalize the parity test to any predicate evaluated on subtree aggregates.

Same pattern

←

Dijkstra: Shortest Reach 2

Continue · Next problem

Find the Nearest Clone

mediumGraphsSometimes asked

Even Tree

Graphs · 24 of 34 · 11 min

You are given a tree (a connected, acyclic, undirected graph) of N nodes labeled 1 to N, rooted at node 1, described by a list of edges. N is even.

Remove as many edges as possible so that every resulting connected component has an even number of nodes. Return the maximum number of edges you can remove.

In plain English

Examples

Example 1

Input: N = 10, edges = [[2,1],[3,1],[4,3],[5,2],[6,1],[7,2],[8,6],[9,8],[10,8]]
Output: 2
Note: Subtree of 3 = {3,4} (size 2) and subtree of 6 = {6,8,9,10} (size 4) are even. Cutting both leaves {1,2,5,7} (size 4). All even → 2 edges removed.

Example 2

Input: N = 4, edges = [[1,2],[2,3],[3,4]]
Output: 1
Note: Only node 3 has an even subtree {3,4} (size 2). Cut edge 2–3 → {3,4} and {1,2}, both even. 1 edge.

Example 3

Input: N = 4, edges = [[1,2],[1,3],[1,4]]
Output: 0
Note: Each leaf's subtree has size 1 (odd). No even non-root subtree exists, so no edge can be cut.

Constraints

2 ≤ N ≤ 100 (and N is even)
The graph is a tree: exactly N − 1 edges, connected, acyclic
Nodes are labeled 1 to N, rooted at node 1
Edges are undirected; build the tree by skipping the parent when recursing
A valid partition always exists because N is even

Clarifying questions4First question: Is N guaranteed even?Explore questions

Q1.Is N guaranteed even?
Yes. If N were odd, no partition into all-even components could exist (the sizes would have to sum to an odd total). Evenness of N is what guarantees a solution.
Q2.Is the input really a tree?
Yes — connected and acyclic with N − 1 edges. That is why every non-root node has a unique parent edge and well-defined subtree.
Q3.Can cutting one edge make another cut invalid?
No. Removing an even subtree leaves an even remainder, so other even subtrees stay even. The cuts are independent — that is the heart of the greedy.
Q4.Does the root's subtree count?
No. The root has no parent edge, so its (size N) subtree can never be detached. Only non-root even subtrees count.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Counting the root's subtree (it has no parent edge to cut), assuming cuts conflict and reaching for DP, or recursing and overflowing the stack on a skewed tree.

How to stand out

Prove the greedy: cutting an even subtree leaves an even remainder because N is even, so the cuts never interfere. Then note the answer is a plain count of even non-root subtrees, computed in O(V).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive DFS Subtree Sizes (Baseline)	`O(V)`	`O(V) recursion stack`	The clearest way to state the idea: a post-order recursion returns each subtree's size, and you count even ones along the way. Then flag the recursion-depth caveat for large trees.	Read
2	Iterative DFS Subtree Sizes (Optimal)Optimal	`O(V)`	`O(V)`	The production-safe version. Compute a traversal order with an explicit stack, then accumulate sizes in reverse — no recursion, so no stack-overflow risk on a deep tree.	Read

Even subtrees that can be detached

How to read it:Subtrees {3,4} (size 2) and {6,8,9,10} (size 4) are even; cutting their parent edges leaves {1,2,5,7} (size 4).

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive DFS Subtree Sizes (Baseline)

TimeO(V)SpaceO(V) recursion stack

The clearest way to state the idea: a post-order recursion returns each subtree's size, and you count even ones along the way. Then flag the recursion-depth caveat for large trees.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Root the tree at node 1. What single number per node tells you whether its parent edge is cuttable?

2Hint 2Explore hint

A subtree's size is 1 plus the sizes of its children's subtrees — a textbook post-order recursion.

3Hint 3Explore hint

While returning each size, if it is even and the node is not the root, increment a cut counter.

A · Core idea

Subtree sizes are the whole game, and a post-order DFS computes them in one sweep.

Why the root is excluded. The root has no parent, hence no edge above it to cut. Its subtree (the whole tree, size N, which is even) is never a separable piece, so it must not be counted.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 4, edges = [[1,2],[2,3],[3,4]]

Interactive diagram

Post-order sizes up a chain

dfs(4)

Active call / nodeSupporting contextReturned stateNot active

Sizes returned bottom-up: 1, 2, 3, 4. Only the size-2 subtree at node 3 is a cut.

Final result1

C · Code with teaching comments

Reference implementation previewprivate List<List<Integer>> adj; private int cuts; public int evenForest(int n, int[][] edges) { adj = new ArrayList<>();Explore the full code

solution.javaJava

Recursive DFS Subtree Sizes (Baseline) — reference

3 teaching notes

1
private List<List<Integer>> adj;
2
private int cuts;
3
 
4
public int evenForest(int n, int[][] edges) {
5
    adj = new ArrayList<>();
6
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
7
    for (int[] e : edges) {
8
        adj.get(e[0]).add(e[1]);
9
        adj.get(e[1]).add(e[0]);
10
    }
11
    cuts = 0;
12
    // Root the tree at node 1; sentinel parent 0 has no real edge.
13
    dfs(1, 0);                       // root at 1, no parent (0)
14
    return cuts;
15
}
16
 
17
private int dfs(int u, int parent) {
18
    int size = 1;
19
    for (int v : adj.get(u)) {
20
        // Treats the undirected edge list as a rooted tree without a visited array.
21
        if (v != parent) {           // skip the edge back to the parent
22
            size += dfs(v, u);
23
        }
24
    }
25
    // Cut the parent edge exactly when the subtree is even and u is not the root.
26
    if (u != 1 && size % 2 == 0) {   // even subtree, not the root → cuttable
27
        cuts++;
28
    }
29
    return size;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(V) timeO(V) recursion stack spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Counting the root's even subtree — it has no parent edge to cut.Explore edge cases

Pitfalls

Counting the root's even subtree — it has no parent edge to cut.
Recursing without a parent guard — infinite loop on the undirected edges.
Deep recursion on a chain — risk of stack overflow; switch to iterative.

03.2

Approach 2 of 2 · Optimal

Iterative DFS Subtree Sizes (Optimal)

TimeO(V)SpaceO(V)

The production-safe version. Compute a traversal order with an explicit stack, then accumulate sizes in reverse — no recursion, so no stack-overflow risk on a deep tree.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The recursion only used the stack to defer a parent until its children finished. Can you get the same post-order effect without the call stack?

2Hint 2Explore hint

Do an iterative DFS from the root recording parents and a visit order. A node always appears before its children in that order.

3Hint 3Explore hint

Walk the order in REVERSE: each node's children are already processed, so its size is final. Count it if even and non-root, then add its size to its parent.

A · Core idea

The logic is identical to the recursion; only the mechanism changes so a deep tree cannot blow the call stack.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 6, edges = [[1,2],[2,3],[3,4],[4,5],[5,6]]

Array state

init

all sizes 1 (index 1..6)

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Iterative DFS Subtree Sizes (Optimal) — optimal

4 teaching notes

1
public int evenForest(int n, int[][] edges) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
4
    for (int[] e : edges) {
5
        adj.get(e[0]).add(e[1]);
6
        adj.get(e[1]).add(e[0]);
7
    }
8
    int[] parent = new int[n + 1];
9
    int[] order = new int[n];
10
    int idx = 0;
11
    Deque<Integer> stack = new ArrayDeque<>();
12
    stack.push(1);
13
    parent[1] = 0;
14
    // An explicit stack records a DFS order with parents — no recursion depth to
15
    // overflow.
16
    while (!stack.isEmpty()) {            // iterative DFS, no stack overflow
17
        int u = stack.pop();
18
        order[idx++] = u;
19
        for (int v : adj.get(u)) {
20
            if (v != parent[u]) {
21
                parent[v] = u;
22
                stack.push(v);
23
            }
24
        }
25
    }
26
    int[] size = new int[n + 1];
27
    Arrays.fill(size, 1);
28
    int cuts = 0;
29
    // Processing the order backward guarantees children are summed before their parent.
30
    for (int i = n - 1; i >= 0; i--) {    // reverse order = post-order
31
        int u = order[i];
32
        // Even, non-root subtree → its parent edge is a valid cut.
33
        if (u != 1 && size[u] % 2 == 0) cuts++;
34
        // Fold the finished subtree size up into the parent; the root's parent is the
35
        // unused index 0.
36
        size[parent[u]] += size[u];       // parent[1]=0 → size[0], harmless
37
    }
38
    return cuts;
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(V) timeO(V) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7N = 2, edges = [[1,2]] — size[2] = 1 (odd) → no cut. A two-node tree is already one even component; answer 0.Explore edge cases

Edge cases handled

N = 2, edges = [[1,2]]size[2] = 1 (odd) → no cut. A two-node tree is already one even component; answer 0.
star: one center, N−1 leavesEvery leaf subtree is size 1 (odd) → 0 cuts unless a leaf chain makes an even subtree.
deep chain of N nodesIterative DFS handles the O(N) depth with no overflow; recursion might not.

Pitfalls

Counting the root (index 1) — exclude it explicitly.
Processing the order forward instead of reversed — parents summed before children, wrong sizes.
Forgetting the parent guard while building the order — would revisit via the undirected edge.
Recursive DFS on a long chain — overflow; the explicit stack avoids it.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting the root

The root has no parent edge, so its subtree (the whole tree, size N) can never be separated. Including it overcounts by one whenever N is even — which it always is here.

Explore the code comparison

Don't write this

if size[u] % 2 == 0:        # also counts the root
    cuts += 1

Write this instead

if u != root and size[u] % 2 == 0:
    cuts += 1

Missing the parent guard

The edges are undirected, so adj[u] includes the parent. Without skipping it, the traversal walks back up and revisits nodes, corrupting subtree sizes (or looping forever).

Explore the code comparison

Don't write this

for (int v : adj.get(u)) {
    size += dfs(v, u);        // recurses back into the parent
}

Write this instead

for (int v : adj.get(u)) {
    if (v != parent) {        // only descend into children
        size += dfs(v, u);
    }
}

Deep recursion overflow

A skewed tree (a chain) has height equal to N. A recursive DFS nests N call frames and can overflow the stack; an explicit-stack iterative DFS keeps that depth on the heap.

Explore the code comparison

Don't write this

def dfs(u, parent):
    size = 1
    for v in adj[u]:
        if v != parent:
            size += dfs(v, u)   # depth = tree height
    return size

Write this instead

stack = [1]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if v != parent[u]:
            parent[v] = u
            stack.append(v)
# accumulate sizes over reversed(order)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Root the tree, DFS subtree sizes, count even non-root subtrees

Code pattern to memorize

root at 1, compute size[u] = 1 + sum(size[child])
answer = number of nodes u (u != root) with size[u] even
# total nodes N is even, so the leftover is always even too

Rules to remember

1The total node count N is even (guaranteed) — that is what makes an all-even partition possible.
2You may cut the parent edge of node u exactly when size[u] is even; count every such non-root node.
3The root has no parent edge, so it never contributes a cut even if size[root] = N is even.
4Cuts are independent: removing one even subtree leaves both pieces even, so greedily taking all of them is optimal.
5Use an iterative DFS (explicit stack) — a deep or skewed tree can overflow a recursive call stack.

Use this pattern when

Tree problems answerable from **subtree sizes** computed in one post-order pass
Partitioning a tree by cutting edges under a parity / size constraint
Greedy cut decisions that are locally safe and globally independent
Any 'remove edges so each piece satisfies P' on a tree where P depends only on subtree counts

Choose another pattern when

The graph has cycles → it is not a tree; subtree sizes are undefined
Cuts interact (one affects another's validity) → greedy fails, needs DP
You need an actual minimum or weighted partition → tree DP over (cut, not-cut) states
Constraint depends on node values, not counts → size alone is insufficient

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Diameter of Binary Tree
Coming soon
Another single post-order pass — combine child heights instead of counting even subtrees.
Tree DP: Maximum Independent Set
Coming soon
When cut decisions interact, move from a greedy count to (include, exclude) tree DP.
Centroid of a Tree
Coming soon
Also driven by subtree sizes — find the node whose removal balances the pieces.
Count of Subtrees With a Given Property
Coming soon
Generalize the parity test to any predicate evaluated on subtree aggregates.

Same pattern

←

Dijkstra: Shortest Reach 2

Continue · Next problem

Find the Nearest Clone