Equal Tree Partition - Solution & Explanation

Problem Overview: You are given a binary tree and can remove exactly one edge. The goal is to determine whether that cut can split the tree into two subtrees whose node values sum to the same total.

The core observation: if the total sum of all nodes is S, you need a subtree whose sum equals S/2. Removing the edge above that subtree creates two trees with equal sums.

Approach 1: Recompute Subtree Sum for Every Edge (Brute Force) (Time: O(n²), Space: O(h))

Consider every edge in the tree as a potential cut. For each edge, compute the sum of nodes in the detached subtree using a DFS traversal, then compare it with the remaining part of the tree. If both sums match, the partition works. This approach repeatedly recalculates subtree sums, causing redundant traversals of the same nodes. It works for small trees but becomes slow for larger inputs since each DFS can take O(n) time and you may try up to O(n) edges.

Approach 2: Single DFS with Subtree Sum Tracking (Optimal) (Time: O(n), Space: O(n))

Run a postorder DFS over the binary tree and compute the sum of every subtree. Store each subtree sum in a hash set or frequency map while returning sums up the recursion stack. After the traversal, you know the total tree sum. If the total is odd, equal partition is impossible. Otherwise check whether a subtree with sum total/2 exists. Cutting the edge above that subtree forms two trees with equal sums.

Handling the edge case where the total sum is zero requires special care. Multiple zero-sum subtrees must exist because removing the edge above the entire tree is not allowed. Tracking subtree frequencies solves this.

This solution performs a single pass using depth-first search and leverages subtree aggregation, a common pattern in tree problems. Postorder traversal ensures children are processed before computing the parent’s sum.

Recommended for interviews: The single DFS subtree-sum approach. Interviewers expect you to recognize that equal partition requires a subtree with half of the total sum. The brute force method demonstrates understanding of the problem structure, but the O(n) DFS solution shows you know how to aggregate information efficiently during traversal.