Equal Tree Partition solution and explanation
4 more videos on this problem
Tree Data Structure | Lecture 23 - Equal Tree PartitionThe Hustling Engineer · 18:31 · 1K views
Equal Tree Partition | interviewBit | Abinash BiswalAbinash Biswal · 16:27 · 953 views
LeetCode 663 - Equal Tree Partition - Amazon Interview Question Solved By Recursion In JavaAlgorithmicIQ · 15:21 · 846 views
663. Equal Tree Partition - Week 3/5 Leetcode June ChallengeProgramming Live with Larry · 12:56 · 351 views
Day 272 - Teaching Kids Programming - Equal Tree Partition via Recursive Depth First SearchDoctor Lai · 11:57 · 106 views
The problem
Given the root of a binary tree, return true if you can partition the tree into two trees with equal sums of values after removing exactly one edge on the original tree.
Example 1:
Input: root = [5,10,10,null,null,2,3] Output: true
Example 2:
Input: root = [1,2,10,null,null,2,20] Output: false Explanation: You cannot split the tree into two trees with equal sums after removing exactly one edge on the tree.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105
Approach overview
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.
Solution
# 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:
def sum(root):
if root is None:
return 0
l, r = sum(root.left), sum(root.right)
seen.append(l + r + root.val)
return seen[-1]
seen = []
s = sum(root)
if s % 2 == 1:
return False
seen.pop()
return s // 2 in seen/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> seen;
public boolean checkEqualTree(TreeNode root) {
seen = new ArrayList<>();
int s = sum(root);
if (s % 2 != 0) {
return false;
}
seen.remove(seen.size() - 1);
return seen.contains(s / 2);
}
private int sum(TreeNode root) {
if (root == null) {
return 0;
}
int l = sum(root.left);
int r = sum(root.right);
int s = l + r + root.val;
seen.add(s);
return s;
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> seen;
bool checkEqualTree(TreeNode* root) {
int s = sum(root);
if (s % 2 != 0) return false;
seen.pop_back();
return count(seen.begin(), seen.end(), s / 2);
}
int sum(TreeNode* root) {
if (!root) return 0;
int l = sum(root->left), r = sum(root->right);
int s = l + r + root->val;
seen.push_back(s);
return s;
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func checkEqualTree(root *TreeNode) bool {
var seen []int
var sum func(root *TreeNode) int
sum = func(root *TreeNode) int {
if root == nil {
return 0
}
l, r := sum(root.Left), sum(root.Right)
s := l + r + root.Val
seen = append(seen, s)
return s
}
s := sum(root)
if s%2 != 0 {
return false
}
seen = seen[:len(seen)-1]
for _, v := range seen {
if v == s/2 {
return true
}
}
return false
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute Subtree Sum for Each Edge (Brute Force) | O(n²) | O(h) | Conceptual baseline or very small trees where repeated DFS is acceptable |
| Single DFS with Subtree Sum Hashing | O(n) | O(n) | General case and interview solution; computes all subtree sums in one traversal |
Frequently asked questions
Is Equal Tree Partition easy or hard?
Equal Tree Partition is generally classified as a Medium difficulty problem. The challenge lies in recognizing the relationship between subtree sums and the total tree sum, then implementing an efficient DFS to compute and track those values.
Equal Tree Partition Python/Java solution
Most implementations perform a recursive DFS that returns subtree sums. During traversal, the algorithm stores each subtree sum in a set or map. The same logic works across Python, Java, C++, and Go because the approach depends on recursion and hash-based lookup.
How to solve Equal Tree Partition in O(n)?
Perform a postorder DFS and compute the sum of each subtree. Store these sums in a set or map while returning the values to parent nodes. After the traversal, compute the total tree sum and check if total/2 exists among the subtree sums (excluding the entire tree). This guarantees linear time complexity.
What is the best approach for Equal Tree Partition?
The most efficient approach uses a postorder DFS to compute the sum of every subtree while storing those sums in a hash set or frequency map. After computing the total tree sum, check whether a subtree with sum equal to half of the total exists. This solution runs in O(n) time and O(n) space because each node is processed once.
Is Equal Tree Partition asked at Google/Amazon/Meta?
Tree partitioning and subtree sum problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test DFS traversal, subtree aggregation, and recognizing when a tree can be split based on computed metrics such as sums or node counts.
What data structure is used in Equal Tree Partition?
The solution relies on a binary tree structure combined with depth-first search traversal. A hash set or hash map is typically used to store subtree sums so the algorithm can quickly check whether a target sum like total/2 exists.
What is the time complexity of Equal Tree Partition?
The optimal solution runs in O(n) time where n is the number of nodes in the binary tree. A single DFS traversal calculates all subtree sums. Space complexity is O(n) due to recursion stack and storage of subtree sums.