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.

Description Solution Video 18:31

663. Equal Tree Partition

Medium42.3% acceptance1 companyPremium elsewhere, free here

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, 10⁴].
-10⁵ <= Node.val <= 10⁵

Asked at 1 company

Amazon

Topics

18:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

663. Equal Tree Partition

Asked at 1 company

Topics

Similar problems