LeetCode 663 - Equal Tree Partition

LeetCode Problem 663

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks whether it is possible to split a binary tree into two separate trees such that both resulting trees have the same sum of node values. The split must happen by removing exactly one edge from the original tree.

A binary tree is given through its root node. Every node contains an integer value, and each node may have a left child and a right child. When an edge is removed, the tree separates into two disconnected components. Each component forms a valid tree, and we must determine whether the sums of values in those two trees are equal.

Another way to think about the problem is this: if the total sum of the entire tree is S, then after removing one edge we need one subtree with sum S / 2, because the remaining part of the tree automatically has sum S - S / 2 = S / 2.

The constraints are important:

• The tree can contain up to 10^4 nodes.
• Node values may be negative.
• Values range from -10^5 to 10^5.

These constraints immediately rule out extremely inefficient approaches. Since the tree can be fairly large, repeatedly recomputing subtree sums from scratch would become too slow.

There are also several important edge cases:

• A tree with only one node cannot be split because there is no edge to remove.
• Trees whose total sum is odd can never be partitioned equally.
• Negative values can create subtree sums that repeat or cancel each other out.
• A total sum of zero requires special handling because multiple zero-sum subtrees may exist.
• The entire tree itself cannot count as one side of the partition because removing an edge must produce two non-empty trees.

Approaches

Brute Force Approach

A straightforward solution is to consider every edge in the tree and simulate removing it. For each possible removal, we compute the sum of the disconnected subtree and compare it with the remaining tree sum.

To do this naively, we can traverse every node and treat the subtree rooted at that node as one side of the partition. For each node, we recursively calculate the subtree sum from scratch.

This approach is correct because every removable edge corresponds to exactly one subtree. If any subtree sum equals half of the total tree sum, then removing the edge connecting that subtree to its parent produces two equal-sum trees.

The problem is efficiency. Suppose the tree contains n nodes. Computing a subtree sum takes O(n) time in the worst case, and doing this for every node leads to O(n^2) complexity. With up to 10^4 nodes, this becomes too slow.

Optimal Approach

The key observation is that subtree sums overlap heavily. Instead of recomputing them repeatedly, we can calculate every subtree sum exactly once using postorder depth-first search.

During a postorder traversal:

• We first compute the left subtree sum.
• Then compute the right subtree sum.
• Finally compute the current node's subtree sum.

As we compute subtree sums, we store them in a hash set or list. Once we know the total tree sum, we only need to check whether any proper subtree has sum equal to half of the total.

This works because removing the edge above a subtree cleanly separates that subtree from the rest of the tree.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Recomputes subtree sums repeatedly
Optimal	O(n)	O(n)	Computes each subtree sum once using DFS

Here, h represents the height of the tree.

Algorithm Walkthrough

1. Start with a postorder depth-first traversal of the tree.

Postorder traversal is important because the sum of a subtree depends on the sums of its children. We must process children before the parent node. 2. For each node, recursively compute the sum of the left subtree.

If the node has no left child, the contribution is 0. 3. Recursively compute the sum of the right subtree.

Similarly, a missing right child contributes 0. 4. Compute the current subtree sum.

The subtree sum is:

$\text{subtreeSum} = \text{node.val} + \text{leftSum} + \text{rightSum}$

Store this value in a list or hash set. 5. Continue until the traversal finishes.

At the end of traversal, the final computed sum is the total sum of the entire tree. 6. Remove the total tree sum from consideration.

The whole tree itself cannot be used as one side of the partition because no edge removal isolates the entire tree. 7. Check whether the total sum is even.

If the total sum is odd, equal partition is impossible because two equal integers cannot add up to an odd number. 8. Search for totalSum / 2 among the stored subtree sums.

If such a subtree exists, removing the edge connecting that subtree to its parent creates two trees with equal sums.

Why it works

Every removable edge corresponds to exactly one subtree. Removing the edge above a subtree separates that subtree from the rest of the tree. Therefore, the problem reduces to determining whether any proper subtree has sum equal to half of the total tree sum.

The postorder DFS guarantees that every subtree sum is computed correctly because child sums are finalized before the parent is processed. Since each subtree sum is computed once and checked once, the algorithm is both correct and efficient.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List

class Solution:
    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False

        subtree_sums: List[int] = []

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            left_sum = dfs(node.left)
            right_sum = dfs(node.right)

            current_sum = node.val + left_sum + right_sum
            subtree_sums.append(current_sum)

            return current_sum

        total_sum = dfs(root)

        # Remove the total sum of the whole tree
        subtree_sums.pop()

        # Equal partition impossible if total sum is odd
        if total_sum % 2 != 0:
            return False

        target = total_sum // 2

        return target in subtree_sums

The implementation follows the exact structure of the optimal algorithm.

The dfs function performs a postorder traversal. For every node, it first computes the left subtree sum and right subtree sum. Once both are known, it calculates the current subtree sum and stores it in subtree_sums.

After the traversal completes, total_sum contains the sum of the entire tree. Since the full tree cannot represent one side of a partition, the last value added to subtree_sums is removed with pop().

The algorithm then checks whether the total sum is even. If it is odd, the answer is immediately False.

Finally, the code searches for total_sum // 2 among the stored subtree sums. If found, a valid partition exists.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func checkEqualTree(root *TreeNode) bool {
    if root == nil {
        return false
    }

    subtreeSums := []int{}

    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftSum := dfs(node.Left)
        rightSum := dfs(node.Right)

        currentSum := node.Val + leftSum + rightSum
        subtreeSums = append(subtreeSums, currentSum)

        return currentSum
    }

    totalSum := dfs(root)

    // Remove total tree sum
    subtreeSums = subtreeSums[:len(subtreeSums)-1]

    if totalSum%2 != 0 {
        return false
    }

    target := totalSum / 2

    for _, sum := range subtreeSums {
        if sum == target {
            return true
        }
    }

    return false
}

The Go implementation mirrors the Python solution closely.

Instead of Python lists, Go uses slices. The subtree sums are stored in a slice named subtreeSums.

Go does not support nested named functions directly, so the recursive DFS is declared using a function variable:

var dfs func(node *TreeNode) int

Nil pointers are handled explicitly using node == nil.

Since Go integer division automatically truncates toward zero, checking totalSum % 2 != 0 first guarantees safe division for the target sum.

Worked Examples

Example 1

Input:

        5
       / \
     10   10
          / \
         2   3

Total sum:

5 + 10 + 10 + 2 + 3 = 30

Target subtree sum:

30 / 2 = 15

Postorder traversal process:

Node	Left Sum	Right Sum	Subtree Sum	Stored Sums
10 (left)	0	0	10	[10]
2	0	0	2	[10, 2]
3	0	0	3	[10, 2, 3]
10 (right)	2	3	15	[10, 2, 3, 15]
5	10	15	30	[10, 2, 3, 15, 30]

Remove total sum 30 from consideration:

[10, 2, 3, 15]

Since 15 exists, removing the edge above the right subtree creates:

Tree 1 sum = 15
Tree 2 sum = 15

Result:

true

Example 2

Input:

        1
       / \
      2   10
         /  \
        2   20

Total sum:

1 + 2 + 10 + 2 + 20 = 35

Since 35 is odd, equal partition is impossible.

The algorithm immediately returns:

false

No further searching is necessary.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(n)	Stores subtree sums and recursion stack

The DFS traversal processes every node exactly one time, giving linear time complexity.

The space usage comes from two sources:

• The recursion stack, which may reach O(h) where h is tree height.
• The subtree_sums list, which stores one sum per node.

In the worst case of a skewed tree, the recursion depth can become O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    5,
    TreeNode(10),
    TreeNode(10, TreeNode(2), TreeNode(3))
)
assert solution.checkEqualTree(root1) == True  # Valid equal partition

# Example 2
root2 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(10, TreeNode(2), TreeNode(20))
)
assert solution.checkEqualTree(root2) == False  # Odd total sum

# Single node tree
root3 = TreeNode(1)
assert solution.checkEqualTree(root3) == False  # Cannot remove any edge

# Simple valid split
root4 = TreeNode(0, TreeNode(0), TreeNode(0))
assert solution.checkEqualTree(root4) == True  # Multiple zero-sum subtrees

# Negative values
root5 = TreeNode(
    -5,
    TreeNode(-5),
    TreeNode(0)
)
assert solution.checkEqualTree(root5) == True  # Negative sums handled correctly

# No valid partition
root6 = TreeNode(
    4,
    TreeNode(1),
    TreeNode(2)
)
assert solution.checkEqualTree(root6) == False  # No subtree equals half

# Skewed tree
root7 = TreeNode(
    1,
    TreeNode(
        1,
        TreeNode(
            1,
            TreeNode(1)
        )
    )
)
assert solution.checkEqualTree(root7) == True  # Deep recursion case

# Total sum zero but no removable partition
root8 = TreeNode(0)
assert solution.checkEqualTree(root8) == False  # Entire tree cannot count

Test	Why
[5,10,10,null,null,2,3]	Standard valid partition case
[1,2,10,null,null,2,20]	Odd total sum case
[1]	Single-node edge case
[0,0,0]	Multiple zero-sum subtrees
[-5,-5,0]	Negative values handling
[4,1,2]	No matching subtree
Skewed tree	Deep recursion structure
[0]	Ensures whole tree is not reused

Edge Cases

Single Node Tree

A tree with only one node cannot be partitioned because there is no edge to remove. A naive implementation might incorrectly think that a subtree sum equal to half the total is enough, but the problem explicitly requires removing an edge.

This implementation handles the case correctly because the only subtree sum stored is the total tree sum itself, which is removed before checking for a valid partition.

Total Sum Equals Zero

Zero is a tricky case because if the total sum is zero, the target subtree sum is also zero. Multiple subtrees may have sum zero, and it is important not to count the entire tree itself.

For example:

    0
   / \
  0   0

The implementation removes the total tree sum from the list before searching, ensuring only proper subtrees are considered.

Negative Node Values

Negative values can create unexpected subtree sums. For instance, positive and negative values may cancel each other out.

A solution that assumes all sums are positive could fail badly here. This implementation works correctly because it treats subtree sums as ordinary integers without making assumptions about sign or ordering.

Highly Skewed Trees

A skewed tree behaves like a linked list and produces maximum recursion depth.

For example:

1
 \
  1
   \
    1

The algorithm still runs in O(n) time because each node is processed once. The recursion stack may grow to O(n) in the worst case, which is already reflected in the space complexity analysis.