Equal Tree Partition

Equal Tree Partition

What is this problem about?

The Equal Tree Partition coding problem asks you to determine if you can remove exactly one edge from a binary tree such that the resulting two subtrees have the same sum of node values. You are given the root of the tree, and the total sum can be positive, negative, or zero.

Why is this asked in interviews?

Amazon and other tech firms use the Equal Tree Partition interview question to evaluate a candidate's mastery of depth-first search interview pattern. It requires calculating subtree sums and identifying if any subtree sum is exactly half of the total tree sum. It’s a test of recursion, state management, and handling edge cases like duplicate sums or zero-sum trees.

Algorithmic pattern used

This is a Post-order DFS problem.

1. Calculate the total sum of the entire tree.
2. If the total sum is odd, it's impossible to split into two equal integer parts (return false).
3. Perform a DFS where each node returns the sum of its subtree.
4. During the DFS, store all subtree sums in a set (excluding the total sum itself, as you must remove an edge, and removing the "root's edge" is not allowed).
5. Check if total_sum / 2 exists in the set.

Example explanation

Suppose the tree is: 5 / 10 10 /
2 3

1. Total Sum: 5 + 10 + 10 + 2 + 3 = 30.
2. Target Sum: 30 / 2 = 15.
3. Subtree Sums:
   • Leaf 2: 2
   • Leaf 3: 3
   • Node 10 (right): 10 + 2 + 3 = 15.
   • Node 10 (left): 10
4. Since 15 is in our list of subtree sums, removing the edge above the right 10 splits the tree into two components of sum 15. Result: True.

Common mistakes candidates make

• Removing the Root: Accidentally including the total sum in the search set, which would falsely return true for a tree that can't be partitioned.
• Integer Division: Not checking if the total sum is divisible by 2.
• Zero Sums: Not correctly handling cases where the total sum is 0 (where half is also 0). You must ensure the 0-sum subtree is an actual descendant and not the root itself.

Interview preparation tip

Subtree sum problems are almost always solved with post-order traversal (bottom-up). Practice this until you can compute and store subtree properties in a single pass.