Equal Tree Partition

Problem Statement

The given requirement is to determine if it's possible to partition a binary tree into two subtrees that have equal sums of their node values. This partitioning is to be performed by removing exactly one edge in the tree. To clarify, the removed edge should result in two separate trees, and the sum of the node values in each subtree should be exactly the same for the function to return true. If no such partition is possible, the function should return false.

Examples

Example 1

Input:

root = [5,10,10,null,null,2,3]

Output:

true

Example 2

Input:

root = [1,2,10,null,null,2,20]

Output:

false

Explanation:

You cannot split the tree into two trees with equal sums after removing exactly one edge on the tree.

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

Approach and Intuition

To solve this problem, we can leverage a recursive depth-first search (DFS) strategy. Here's a summarized approach of the steps you'll likely undertake:

1. Calculate the total sum of all node values in the tree. This first pass will help in determining the target sum for each potential subtree, which should be half of the total sum.

2. Traverse the tree again, this time calculating the cumulative sum of node values as you progress through each node. During this traversal, check if the sum for any subtree (resulting from the hypothetical removal of the edge leading to this subtree) matches half of the total tree sum.

3. If such a sum is found during the traversal, return true indicating that the tree can indeed be split into two with equal sums by removing one edge. If the traversal completes without finding such a match, return false.

Intuitive Breakdown

• Total Sum Calculation: Before deciding where to split, understand the entire tree's weight to determine if it's even theoretically possible to split it evenly (the sum must be even).

• Traversing and Matching: As you traverse, each node's subtree presents a potential breaking point. Calculate if detaching this subtree could yield an even partition.

This approach ensures that you check all possible partitions efficiently using the nature of DFS, where you explore each possibility by diving deep into one path before backtracking and trying others. Each subtree’s sum is essentially checked against a necessary condition for a valid split, which is an optimal way to minimize unnecessary calculations.

Solutions

class Solution {
    Stack<Integer> subtreesSum;
    public boolean checkEqualTree(TreeNode root) {
        subtreesSum = new Stack<>();
        int totalSum = computeTotalSum(root);
        subtreesSum.pop();
        if (totalSum % 2 == 0) {
            for (int sum : subtreesSum) {
                if (sum == totalSum / 2) {
                    return true;
                }
            }
        }
        return false;
    }

    public int computeTotalSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        subtreesSum.push(computeTotalSum(node.left) + computeTotalSum(node.right) + node.val);
        return subtreesSum.peek();
    }
}