deepSWE.io

Equal Tree Partition

Trees

Problem Statement

Given the `root` of a binary tree, return `true` if you can partition the tree into two subtrees with equal sum of values, and `false` otherwise.

Example

Output: true

Explanation: The sum of the whole tree is 30. If we cut the edge between the root (5) and its left child (10), we get two subtrees with sums 10 and 20. This doesn't work. If we cut the edge between the node (10) and its children (2, 3), we get a subtree with sum 5, and the rest of the tree has sum 25. This doesn't work. If we cut the edge between the root (5) and its right child (10), we get two subtrees with sums 15 and 15. This works.

Algorithm Explanation

To solve this problem, we first need to find the sum of the entire tree. Then, we can traverse the tree again, and for each subtree, check if its sum is equal to half of the total sum.

Algorithm Steps

Calculate Total Sum: First, traverse the tree to calculate the sum of all node values. If the total sum is odd, it's impossible to partition it into two equal halves, so we can return `false`.
DFS for Partition: We'll use a second DFS traversal. This function will calculate the sum of the subtree rooted at the current node.
Check for Half Sum: In our second DFS, as we calculate the sum of each subtree, we check if it's equal to `total_sum / 2`. If we find such a subtree (and it's not the entire tree itself), we've found a valid partition.

Calculating Sum

Visiting node 5

Seen Subtree Sums

Total Sum: 0

Equal Tree Partition Solution


class Solution:
    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:
        self.seen = []
        total = self.sum(root)
        self.seen.pop() # Remove the sum of the whole tree
        return total / 2.0 in self.seen

    def sum(self, node):
        if not node:
            return 0
        s = node.val + self.sum(node.left) + self.sum(node.right)
        self.seen.append(s)
        return s