Skip to main content
Talentd

Equal Tree Partition - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Tree5 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 HashingO(n)O(n)General case and interview solution; computes all subtree sums in one traversal

Video Solution

Tree Data Structure | Lecture 23 - Equal Tree Partition • The Hustling Engineer • 1,509 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Equal Tree Partition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Create Components With Same Value