Equal Tree Partition - Leetcode Solution

Problem:

Given a binary tree with n nodes, your task is to check if it’s possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.

Example: Input:
5 /
10 10 /
2 3

Output: True

Explanation: 5 / 10

Sum: 15

10 /
2 3

Sum: 15

Approach:

The approach to solve this problem is to calculate the sum of the entire tree, and then recursively traverse the tree to check if there exists a subtree with the sum equal to the half of the total sum. While traversing the tree, we can keep track of the sum of the subtrees encountered at that level of recursion to avoid re-calculating the sum multiple times.

After finding such a subtree, we can check if the sum of the remaining nodes of the tree (i.e. total tree sum - subtree sum) is equal to the sum of the subtree. If this condition satisfies, then that subtree can be cut from the tree to get two equal sums of the remaining nodes.

Algorithm:

1. Calculate the total sum of the given tree.
2. Recursively traverse the tree to check if there is a subtree with the sum sum/2.
3. While traversing the tree, keep track of the sum calculated so far at that level of recursion.
4. If a subtree with the sum sum/2 is found, return true and check if the sum of the remaining nodes of the tree is equal to the sum of the subtree.
5. If the above condition satisfies, return true.
6. If no such subtree is found, return false.

Implementation:

Here is the Python3 implementation of the above approach:

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

class Solution:
    def findEqualTreePartition(self, root: TreeNode) -> bool:
        # function to calculate the sum of the entire tree
        def calcSum(root):
            if not root:
                return 0
            return root.val + calcSum(root.left) + calcSum(root.right)
        
        # function to recursively traverse the tree and find the subtree with sum sum/2
        def dfs(root, target, currSum, vis):
            if not root:
                return False
            if root in vis:
                return False
            vis.add(root)
            leftSubTreeSum = dfs(root.left, target, currSum, vis)
            rightSubTreeSum = dfs(root.right, target, currSum, vis)
            currSubTreeSum = root.val + leftSubTreeSum + rightSubTreeSum
            if currSubTreeSum == target:
                return True
            return False 
        
        totalSum = calcSum(root)
        if totalSum % 2 != 0:
            return False
        target = totalSum // 2
        vis = set()
        return dfs(root, target, 0, vis)

Time Complexity:

The time complexity of the above approach is O(n) since we are traversing the entire tree only once.

Space Complexity:

The space complexity is O(n) since we are using a visited set to avoid revisiting the same nodes during traversal. In the worst case where the tree is skewed and has only one child, the space complexity can go up to O(n).

1