Split Binary Tree

Tags

Split Binary Tree

Category

Binary Trees

Difficulty

Medium

Problem Statement

Given a binary tree with integer values, determine if the tree can be split into two subtrees with equal sums by removing a single edge. Removing an edge splits the tree into two components: the subtree rooted at the child node where the edge was removed, and the rest of the tree. Return true if such a split exists.

Intuition

If the total sum of the tree is S, then removing an edge creates two parts. For them to be equal, each must sum to S/2. This means S must be even. We then need to find any subtree whose sum equals S/2. If such a subtree exists, removing the edge connecting it to its parent produces the desired equal split.

Approach

  1. Compute the total sum of the entire tree.
  2. If the total sum is odd, return false immediately (cannot split into two equal integer sums).
  3. Define a recursive function that computes the sum of each subtree.
  4. During the traversal, check if any subtree sum equals totalSum / 2.
  5. If found, return true. The edge above that subtree is the one to remove.
  6. Be careful not to count the root itself as a valid split (removing the "edge" above the root does not create two trees).

Pseudocode

function splitBinaryTree(root):
    totalSum = computeSum(root)
    if totalSum % 2 != 0:
        return false
    targetHalf = totalSum / 2
    found = false

    function subtreeSum(node):
        if node is null:
            return 0
        leftSum = subtreeSum(node.left)
        rightSum = subtreeSum(node.right)
        currentSum = node.value + leftSum + rightSum
        if currentSum == targetHalf and node != root:
            found = true
        return currentSum

    subtreeSum(root)
    return found

Note: Even checking at the root is acceptable if we realize that if the root's total equals targetHalf, then targetHalf = totalSum / 2 = targetHalf, which means totalSum = 2 * targetHalf, and the root sum is targetHalf. But the "other" part would be 0, which also equals targetHalf only if targetHalf = 0. A simpler implementation allows checking at any node including root, since if root sum = targetHalf, then totalSum = 2 * targetHalf and removing the root edge yields sums of targetHalf and targetHalf (which is 0), but that contradicts unless both are 0.

A cleaner approach: check all non-root subtrees.

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. We traverse every node once to compute the total sum and once more (or in the same pass) to find a matching subtree.
  • Space: O(h) where h is the height of the tree, for the recursion stack.

Key Insights

  • The total sum must be even for a valid split to exist.
  • Finding a subtree with sum = totalSum / 2 guarantees the remaining part also sums to totalSum / 2.
  • A single DFS pass can both compute subtree sums and check the condition.
  • Negative values in the tree are allowed and the algorithm still works correctly.

Edge Cases

  • Single node: cannot remove any edge, return false (unless we define the problem differently).
  • Tree with total sum 0: every subtree with sum 0 creates a valid split. The two empty-sum parts are equal.
  • Tree with all zeros: any edge removal creates two equal-sum (0) parts.
  • Tree with negative values: the sum can still be even and a valid split may exist.
  • Two-node tree where both nodes have the same value: removing the edge between them creates equal halves.
  • Odd total sum: immediately return false.

Linked mentions