Problem Description

You are given the root of a binary tree. Your task is to determine if it's possible to split the tree into two separate trees by removing exactly one edge, such that both resulting trees have equal sums of node values.

The problem asks you to return true if such a partition exists, and false otherwise.

For example, if you have a tree where removing one edge creates two subtrees - one with nodes summing to 10 and another with nodes summing to 10 - then you would return true. However, if no such edge removal can create two equal-sum subtrees, you would return false.

The solution works by first calculating the sum of all nodes in the entire tree. If this total sum is odd, it's impossible to split it into two equal parts, so we return false immediately. If the sum is even, we need to find if there exists a subtree with sum equal to total_sum / 2.

The code uses a depth-first search to calculate subtree sums, storing each subtree sum in a list called seen. It then checks if total_sum / 2 exists in this list (excluding the root's sum itself, since we need to remove an edge, not include the entire tree). If such a subtree exists, removing the edge connecting it to its parent would create the desired equal partition.

Flowchart Walkthrough

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

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we need to examine the relationship between nodes and their subtrees.

DFS

• Yes: We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using a DFS approach for this problem.

This makes perfect sense for Equal Tree Partition because:

1. We need to traverse the entire tree to calculate subtree sums
2. DFS allows us to process each subtree completely before moving to siblings
3. The recursive nature of DFS naturally calculates subtree sums from bottom-up (leaves to root)
4. We can efficiently track all subtree sums during a single DFS traversal
5. The problem requires examining every possible edge removal, which corresponds to checking every subtree sum

The DFS pattern is ideal here as it lets us compute and store all subtree sums in one pass, then check if any of these sums equals half of the total tree sum (which would indicate a valid partition point).

Intuition

The key insight is that if we remove one edge from a tree, we split it into exactly two parts: one subtree and the remaining tree. For these two parts to have equal sums, each part must have a sum equal to total_sum / 2.

Think about it this way: if the total sum of all nodes is S, and we want to split it into two equal parts, each part must have sum S/2. This immediately tells us that if S is odd, it's impossible to create equal partitions.

When we remove an edge between a parent and child node, the child's subtree becomes one partition, and everything else becomes the other partition. So the question becomes: does there exist a subtree in our tree whose sum equals total_sum / 2?

To find this, we can use DFS to calculate the sum of every subtree in the tree. As we traverse from bottom to top, at each node we calculate: subtree_sum = node.val + left_subtree_sum + right_subtree_sum. We store all these subtree sums as we calculate them.

There's one subtle but important detail: we need to exclude the root's sum from our check. Why? Because the root's sum is the total sum of the entire tree - if we "remove" an edge above the root, we wouldn't be splitting the tree at all. We'd just have the entire tree on one side and nothing on the other.

So our approach is:

1. Calculate all subtree sums using DFS, storing them in a list
2. If the total sum is odd, return false
3. Remove the last element (root's sum) from our list
4. Check if total_sum / 2 exists in our list of subtree sums

If we find such a subtree, removing the edge connecting it to its parent creates the equal partition we're looking for.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS function to traverse the tree and calculate subtree sums. Here's how the solution works step by step:

1. Define the DFS helper function sum(root):

• Base case: If the current node is None, return 0
• Recursively calculate the sum of left subtree: l = sum(root.left)
• Recursively calculate the sum of right subtree: r = sum(root.right)
• Calculate current subtree sum: current_sum = l + r + root.val
• Store this subtree sum in the seen list
• Return the current subtree sum

2. Initialize data structures:

• Create an empty list seen to store all subtree sums encountered during traversal

3. Calculate the total tree sum:

• Call s = sum(root) to traverse the entire tree
• This populates the seen list with all subtree sums, including the root's sum

4. Check for odd total sum:

• If s % 2 == 1, it's impossible to split into equal parts, return False

5. Remove the root's sum:

• Execute seen.pop() to remove the last element (root's total sum)
• We exclude this because we need to actually remove an edge, not keep the entire tree intact

6. Check for valid partition:

• Return s // 2 in seen
• This checks if any subtree has exactly half the total sum
• If such a subtree exists, removing the edge above it creates two equal partitions

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once

Space Complexity: O(n) for storing the seen list and the recursion call stack

The elegance of this solution lies in recognizing that we only need to find one subtree with sum equal to total_sum / 2. The DFS pattern naturally computes all subtree sums in a single traversal, making this an efficient one-pass solution.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Consider this binary tree:

        5
       / \
      10  10
     / \
    2   3

Step 1: Calculate all subtree sums using DFS

Starting from the leaves and working up:

• Node with value 2: subtree sum = 2 (no children)
• Node with value 3: subtree sum = 3 (no children)
• Node with value 10 (right): subtree sum = 10 (no children)
• Node with value 10 (left): subtree sum = 10 + 2 + 3 = 15
• Node with value 5 (root): subtree sum = 5 + 15 + 10 = 30

As we calculate each sum, we add it to our seen list: seen = [2, 3, 15, 10, 30]

Step 2: Check if total sum is even

Total sum = 30 (even) ✓ Target sum for each partition = 30 / 2 = 15

Step 3: Remove root's sum from consideration

After seen.pop(): seen = [2, 3, 15, 10]

Step 4: Check if target sum exists in remaining subtrees

Is 15 in seen? Yes! The left subtree rooted at node 10 has sum 15.

Step 5: Verify the partition

If we remove the edge between root (5) and its left child (10):

• Left partition: subtree with nodes {10, 2, 3}, sum = 15
• Right partition: remaining tree with nodes {5, 10}, sum = 15

Both partitions have equal sums, so we return true.

Why this works: When we found a subtree with sum 15 (half of total), we knew that removing the edge above it would leave the rest of the tree with sum 30 - 15 = 15, creating two equal partitions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm performs a depth-first traversal of the tree using the recursive sum function. Each node is visited exactly once during this traversal. At each node, the operations performed are:

• Recursive calls to left and right children
• Addition operations (l + r + root.val)
• Appending to the list (seen.append()) which is O(1)

Since we visit each node once and perform constant time operations at each node, the overall time complexity is O(n).

Space Complexity: O(n) where n is the number of nodes in the binary tree.

The space complexity consists of two components:

1. Recursion call stack: In the worst case (skewed tree), the recursion depth can be O(n). In the best case (balanced tree), it would be O(log n).
2. Auxiliary space for seen list: The list stores the subtree sum for each node in the tree, which requires O(n) space as we store one sum value for each of the n nodes.

The dominant factor is the seen list which always requires O(n) space regardless of tree structure, making the overall space complexity O(n).

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

Common Pitfalls

Pitfall 1: Not Handling Zero Sum Edge Case

The most critical pitfall in this problem occurs when the total tree sum is zero. Consider a tree with values like [0, -1, 1]. The total sum is 0, and half of that is also 0. If we have a subtree with sum 0, the algorithm would incorrectly return True even when we haven't actually removed any edge (since an empty subtree also has sum 0).

Problem Example:

    0
   / \
  -1  1

• Total sum = 0
• Target sum = 0 // 2 = 0
• The subtree rooted at node 0 has sum 0
• But we can't "remove" the root itself - we need to remove an edge

Solution: Instead of just checking if target_sum in subtree_sums, we need to ensure we're actually removing a valid edge. One approach is to track subtree sums with their counts:

def checkEqualTree(self, root: TreeNode) -> bool:
    from collections import Counter
  
    def calculate_subtree_sum(node):
        if node is None:
            return 0
      
        left_sum = calculate_subtree_sum(node.left)
        right_sum = calculate_subtree_sum(node.right)
        current_sum = left_sum + right_sum + node.val
      
        # Only add non-root subtree sums
        if node != root:
            subtree_sums.append(current_sum)
      
        return current_sum
  
    subtree_sums = []
    total_sum = calculate_subtree_sum(root)
  
    if total_sum % 2 == 1:
        return False
  
    target = total_sum // 2
    return target in subtree_sums

Pitfall 2: Integer Overflow in Other Languages

While Python handles arbitrarily large integers, in languages like Java or C++, calculating subtree sums could cause integer overflow for very large node values.

Solution: Use appropriate data types (like long in Java) or implement overflow checking:

# Python doesn't have this issue, but for awareness:
# In Java, you'd use: long currentSum = (long)left + right + node.val;

Pitfall 3: Modifying the Original Tree Structure

Some developers might accidentally modify the tree structure during traversal or forget that we need to preserve the original tree.

Solution: Ensure your DFS function only reads values and doesn't modify any node connections. The current solution correctly avoids this by only reading values and building a separate list.