We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Equal Tree Partition

Number: 663

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given the root of a binary tree, determine if it is possible to split the tree into two trees with equal sum of node values by removing exactly one edge.

Key Insights

  • The overall sum of all nodes in the tree must be even; otherwise, it is impossible to partition the tree into two parts with equal sums.
  • Perform a DFS (Depth First Search) to compute the sum of each subtree.
  • If any subtree (excluding the entire tree) has a sum equal to half of the total sum, then removing the edge connecting this subtree with the rest of the tree will partition the tree into two parts with equal sum.
  • Special case: If the total sum is zero, then care must be taken because multiple subtrees might sum to zero. Ensure that the found zero subtree is not the whole tree.

Space and Time Complexity

Time Complexity: O(n) - We traverse each node once. Space Complexity: O(n) - In the worst case, the recursion stack and storage for subtree sums may require O(n) space.

Solution

We start by computing the total sum of the tree by performing a DFS. If the total sum is odd, return false immediately because an equal partition is impossible. Next, traverse the tree again (or within the same pass) to compute the sum of every subtree. For each subtree (except the whole tree), check if its sum equals half of the total sum. Return true if such a subtree is found. Use recursion for DFS, and be careful when handling the special case when the total sum is zero by ensuring there is at least one valid subtree (apart from the whole tree) that also sums to zero.

Code Solutions

# 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

class Solution:
    def checkEqualTree(self, root: TreeNode) -> bool:
        # List to store subtree sums for later verification
        self.subtree_sums = []
        
        # Compute total sum of the tree using DFS
        def dfs(node):
            if not node:
                return 0
            # Sum of the left subtree, right subtree, and current node's value
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            current_sum = node.val + left_sum + right_sum
            # Append current subtree sum (even for the whole tree, we'll exclude later)
            self.subtree_sums.append(current_sum)
            return current_sum
        
        total_sum = dfs(root)
        # Remove the total sum for the whole tree to avoid false positive
        self.subtree_sums.pop()
        
        # Check if any subtree equals half of total sum
        if total_sum % 2 != 0:
            return False
        
        half = total_sum // 2
        # Return true if one of the subtree sums equals half the total
        return half in self.subtree_sums

# Example usage:
# root = TreeNode(5, TreeNode(10), TreeNode(10, TreeNode(2), TreeNode(3)))
# sol = Solution()
# print(sol.checkEqualTree(root))  # Expected output: True
← Back to All Questions