Maximum Edge Removal for Even Subtrees

Problem

You are given a tree with an even number of nodes. Consider each connection between a parent and child node to be an “edge”. You would like to remove some of these edges, such that the disconnected subtrees that remain each have an even number of nodes.

For example, suppose your input was the following tree:

In this case, removing the edge (3, 4) satisfies our requirement.

Write a function that returns the maximum number of edges you can remove while still satisfying this requirement.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: 
Tree represented as edges: [[1,2], [1,3], [3,4], [3,5], [4,6], [4,7], [4,8]]
Total nodes: 8
Output: 1
Explanation:
The tree has 8 nodes (even). We can remove edge (3,4) to create:
- Subtree rooted at 1: {1,2,3,5} = 4 nodes (even)
- Subtree rooted at 4: {4,6,7,8} = 4 nodes (even)
Maximum edges removed: 1

Example 2

1
2
3
4
5
6
7
8


Input:
Tree represented as edges: [[1,2], [1,3], [2,4], [2,5], [3,6], [3,7]]
Total nodes: 7
Output: 0
Explanation:
The tree has 7 nodes (odd). Since we start with odd total nodes,
it's impossible to split into multiple subtrees where each has even nodes.
No edges can be removed.

Example 3

1
2
3
4
5
6


Input:
Tree represented as edges: [[1,2], [1,3], [1,4], [1,5], [1,6], [1,7]]
Total nodes: 7
Output: 0
Explanation:
Tree has 7 nodes (odd total). Cannot split into even-sized subtrees.

Example 4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


Input:
Tree represented as edges: [[1,2], [2,3], [3,4], [4,5], [4,6]]
Total nodes: 6
Output: 2
Explanation:
Tree: 1-2-3-4-5
           \-6
We can remove edges (2,3) and (4,5):
- Subtree {1,2}: 2 nodes (even)
- Subtree {3,4,6}: 3 nodes (odd) - invalid
Better: Remove (3,4) and (4,6):
- Subtree {1,2,3}: 3 nodes (odd) - invalid
Optimal: Remove (2,3) and (4,6):
- Subtree {1,2}: 2 nodes (even)
- Subtree {3,4,5}: 3 nodes (odd) - invalid
Actually optimal: Remove (3,4):
- Subtree {1,2,3}: 3 nodes (odd) - invalid
Correct optimal: Remove (4,5) and (4,6):
- Subtree {1,2,3,4}: 4 nodes (even)
- Subtree {5}: 1 node (odd) - invalid
True optimal: Remove (2,3):
- Subtree {1,2}: 2 nodes (even)  
- Subtree {3,4,5,6}: 4 nodes (even)
Maximum edges removed: 1

Example 5

1
2
3
4
5
6


Input:
Tree represented as edges: [[1,2], [1,3], [2,4], [2,5], [3,6], [3,7], [4,8], [4,9]]
Total nodes: 9
Output: 0
Explanation:
Tree has 9 nodes (odd). Cannot partition into subtrees where all have even nodes.

Solution

Method 1 - DFS with Subtree Size Calculation

Intuition

To remove an edge and create even-sized subtrees, we need to understand that removing an edge between nodes u and v splits the tree into two parts: the subtree rooted at v and the remaining tree. For both parts to have even sizes, the subtree rooted at v must have even size (and consequently the remaining part will also have even size since total is even). We can use DFS to calculate subtree sizes and count how many subtrees have even sizes.

Approach

Build an adjacency list representation of the tree from the edges
Use DFS to traverse the tree and calculate the size of each subtree
For each node, if its subtree has even size, we can potentially remove the edge connecting it to its parent
Count the number of such removable edges
Handle the edge case where the total number of nodes is odd (return 0)
The root node cannot be removed, so subtract 1 from count if root subtree is even

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


class Solution {
private:
    vector<vector<int>> adj;
    int removableEdges;
    
    int dfs(int node, int parent) {
        int size = 1;
        for (int child : adj[node]) {
            if (child != parent) {
                size += dfs(child, node);
            }
        }
        
        // If subtree has even size and it's not root, we can remove edge to parent
        if (size % 2 == 0 && parent != -1) {
            removableEdges++;
        }
        
        return size;
    }
    
public:
    int maxEdgeRemoval(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        
        // If total nodes is odd, impossible to split into even subtrees
        if (n % 2 == 1) return 0;
        
        adj.resize(n + 1);
        removableEdges = 0;
        
        // Build adjacency list
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        // Start DFS from node 1 (assuming 1-indexed)
        dfs(1, -1);
        
        return removableEdges;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


func maxEdgeRemoval(edges [][]int) int {
    n := len(edges) + 1
    
    // If total nodes is odd, impossible to split into even subtrees
    if n%2 == 1 {
        return 0
    }
    
    // Build adjacency list
    adj := make([][]int, n+1)
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }
    
    removableEdges := 0
    
    var dfs func(node, parent int) int
    dfs = func(node, parent int) int {
        size := 1
        for _, child := range adj[node] {
            if child != parent {
                size += dfs(child, node)
            }
        }
        
        // If subtree has even size and it's not root, we can remove edge to parent
        if size%2 == 0 && parent != -1 {
            removableEdges++
        }
        
        return size
    }
    
    // Start DFS from node 1
    dfs(1, -1)
    
    return removableEdges
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution {
    private List<List<Integer>> adj;
    private int removableEdges;
    
    private int dfs(int node, int parent) {
        int size = 1;
        for (int child : adj.get(node)) {
            if (child != parent) {
                size += dfs(child, node);
            }
        }
        
        // If subtree has even size and it's not root, we can remove edge to parent
        if (size % 2 == 0 && parent != -1) {
            removableEdges++;
        }
        
        return size;
    }
    
    public int maxEdgeRemoval(int[][] edges) {
        int n = edges.length + 1;
        
        // If total nodes is odd, impossible to split into even subtrees
        if (n % 2 == 1) return 0;
        
        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        removableEdges = 0;
        
        // Build adjacency list
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        
        // Start DFS from node 1
        dfs(1, -1);
        
        return removableEdges;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution:
    def max_edge_removal(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        
        # If total nodes is odd, impossible to split into even subtrees
        if n % 2 == 1:
            return 0
        
        # Build adjacency list
        adj = [[] for _ in range(n + 1)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        self.removable_edges = 0
        
        def dfs(node: int, parent: int) -> int:
            size = 1
            for child in adj[node]:
                if child != parent:
                    size += dfs(child, node)
            
            # If subtree has even size and it's not root, we can remove edge to parent
            if size % 2 == 0 and parent != -1:
                self.removable_edges += 1
            
            return size
        
        # Start DFS from node 1
        dfs(1, -1)
        
        return self.removable_edges

Complexity

⏰ Time complexity: O(n), where n is the number of nodes. We visit each node exactly once during DFS
🧺 Space complexity: O(n), for the adjacency list and recursion stack depth in worst case (linear tree)

Method 2 - Bottom-Up DP with Subtree Size Tracking

Intuition

We can think of this problem as a dynamic programming approach where we calculate subtree sizes bottom-up. For each node, if its subtree size is even, removing the edge to its parent creates two even-sized components. We track the number of such possible cuts.

Approach

Build the tree structure using adjacency lists
Use post-order DFS to calculate subtree sizes from leaves to root
For each node, determine if cutting the edge to its parent results in even-sized subtrees
Use memoization to store subtree sizes and avoid recalculation
Count all valid cuts (excluding the root since it has no parent edge)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


class Solution {
private:
    vector<vector<int>> adj;
    vector<int> subtreeSize;
    int totalNodes;
    int validCuts;
    
    int calculateSubtreeSize(int node, int parent) {
        if (subtreeSize[node] != -1) return subtreeSize[node];
        
        int size = 1;
        for (int child : adj[node]) {
            if (child != parent) {
                size += calculateSubtreeSize(child, node);
            }
        }
        
        subtreeSize[node] = size;
        
        // Check if we can cut the edge between this node and its parent
        if (parent != -1 && size % 2 == 0) {
            validCuts++;
        }
        
        return size;
    }
    
public:
    int maxEdgeRemovalDP(vector<vector<int>>& edges) {
        totalNodes = edges.size() + 1;
        
        if (totalNodes % 2 == 1) return 0;
        
        adj.resize(totalNodes + 1);
        subtreeSize.resize(totalNodes + 1, -1);
        validCuts = 0;
        
        // Build adjacency list
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        calculateSubtreeSize(1, -1);
        
        return validCuts;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


func maxEdgeRemovalDP(edges [][]int) int {
    totalNodes := len(edges) + 1
    
    if totalNodes%2 == 1 {
        return 0
    }
    
    adj := make([][]int, totalNodes+1)
    subtreeSize := make([]int, totalNodes+1)
    for i := range subtreeSize {
        subtreeSize[i] = -1
    }
    
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }
    
    validCuts := 0
    
    var calculateSubtreeSize func(node, parent int) int
    calculateSubtreeSize = func(node, parent int) int {
        if subtreeSize[node] != -1 {
            return subtreeSize[node]
        }
        
        size := 1
        for _, child := range adj[node] {
            if child != parent {
                size += calculateSubtreeSize(child, node)
            }
        }
        
        subtreeSize[node] = size
        
        // Check if we can cut the edge between this node and its parent
        if parent != -1 && size%2 == 0 {
            validCuts++
        }
        
        return size
    }
    
    calculateSubtreeSize(1, -1)
    
    return validCuts
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


class Solution {
    private List<List<Integer>> adj;
    private int[] subtreeSize;
    private int validCuts;
    
    private int calculateSubtreeSize(int node, int parent) {
        if (subtreeSize[node] != -1) return subtreeSize[node];
        
        int size = 1;
        for (int child : adj.get(node)) {
            if (child != parent) {
                size += calculateSubtreeSize(child, node);
            }
        }
        
        subtreeSize[node] = size;
        
        // Check if we can cut the edge between this node and its parent
        if (parent != -1 && size % 2 == 0) {
            validCuts++;
        }
        
        return size;
    }
    
    public int maxEdgeRemovalDP(int[][] edges) {
        int totalNodes = edges.length + 1;
        
        if (totalNodes % 2 == 1) return 0;
        
        adj = new ArrayList<>();
        for (int i = 0; i <= totalNodes; i++) {
            adj.add(new ArrayList<>());
        }
        
        subtreeSize = new int[totalNodes + 1];
        Arrays.fill(subtreeSize, -1);
        validCuts = 0;
        
        // Build adjacency list
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        
        calculateSubtreeSize(1, -1);
        
        return validCuts;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution:
    def max_edge_removal_dp(self, edges: List[List[int]]) -> int:
        total_nodes = len(edges) + 1
        
        if total_nodes % 2 == 1:
            return 0
        
        adj = [[] for _ in range(total_nodes + 1)]
        subtree_size = [-1] * (total_nodes + 1)
        
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        self.valid_cuts = 0
        
        def calculate_subtree_size(node: int, parent: int) -> int:
            if subtree_size[node] != -1:
                return subtree_size[node]
            
            size = 1
            for child in adj[node]:
                if child != parent:
                    size += calculate_subtree_size(child, node)
            
            subtree_size[node] = size
            
            # Check if we can cut the edge between this node and its parent
            if parent != -1 and size % 2 == 0:
                self.valid_cuts += 1
            
            return size
        
        calculate_subtree_size(1, -1)
        
        return self.valid_cuts

Complexity

⏰ Time complexity: O(n), where n is the number of nodes. Each node is visited once and memoization prevents recalculation
🧺 Space complexity: O(n), for adjacency list, memoization array, and recursion stack

Notes

Both methods solve the problem by identifying subtrees with even sizes that can be separated from the main tree
The key insight is that removing an edge creates two components, and both must have even sizes for the removal to be valid
If the total number of nodes is odd, it’s impossible to partition into multiple even-sized subtrees
Method 1 is more straightforward with direct DFS traversal
Method 2 adds memoization which can be beneficial for trees with overlapping subproblems (though less common in tree problems)
The problem assumes nodes are numbered starting from 1, but can be easily adapted for 0-indexed nodes
Time complexity is optimal since we need to examine each node at least once
The solution works for any tree structure and handles edge cases like linear trees or star-shaped trees

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - DFS with Subtree Size Calculation#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Bottom-Up DP with Subtree Size Tracking#

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - DFS with Subtree Size Calculation

Intuition

Approach

Code

Complexity

Method 2 - Bottom-Up DP with Subtree Size Tracking

Intuition

Approach

Code

Complexity

Notes