Equal Tree Partition - Practice Coding Problems

Equal Tree Partition - 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.

A partition means dividing the tree into two separate connected components. When you remove an edge, you get two subtrees - the removed subtree and the remaining tree. Both must have the same sum of node values.

Note: You cannot remove the edge above the root node (since there isn't one).

Input & Output

Example 1 — Valid Partition

$ Input: root = [5,10,10,null,null,2,3]

› Output: true

💡 Note: Original tree sum = 5+10+10+2+3 = 30. We can remove the edge above the right subtree (10,2,3) which has sum 15, leaving the left part (5,10) with sum 15. Both parts have equal sum 15.

Example 2 — No Valid Partition

$ Input: root = [1,2,10,null,null,2,20]

› Output: false

💡 Note: Original tree sum = 1+2+10+2+20 = 35. Since 35 is odd, we cannot split it into two equal parts. Any partition would result in unequal sums.

Example 3 — Single Split Works

$ Input: root = [2,1,1]

› Output: true

💡 Note: Tree sum = 2+1+1 = 4. We can remove edge to left child (value 1), creating partitions with sums 1 and 3. Wait, that's not equal. Actually, removing edge to right child gives us partition sums 1 and 3. This should be false, but let me recalculate: we need sum 2 on each side. Remove left subtree (sum 1) leaves right side with sum 3. This doesn't work.

Constraints

The number of nodes in the tree is in the range [1, 10⁴].
-10⁵ ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values [5,10,10,null,null,2,3]

Find Target

Calculate total sum (30) and target sum (15)

Check Partition

Find subtree with sum 15, remove its parent edge

Key Takeaway

🎯 Key Insight: A tree can be equally partitioned if any subtree has exactly half the total sum

Asked in

f Facebook 25 a Amazon 15 M Microsoft 12

The key insight is that we can partition a tree into two equal-sum parts if any subtree has exactly half the total sum. The optimal approach uses DFS to calculate all subtree sums in O(n) time and checks if any equals totalSum/2. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Memoization	O(n)	O(n)	Use DFS to calculate subtree sums efficiently with single traversal
Brute Force - Calculate All Subtree Sums	O(n²)	O(h)	For each node, calculate its subtree sum and check if it equals half the total sum

DFS with Memoization — Algorithm Steps

Step 1: DFS to calculate total sum
Step 2: DFS again, storing each subtree sum
Step 3: Check if any stored subtree sum equals totalSum/2

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit each node and calculate its subtree sum

Store Sums

Store each subtree sum in a set for lookup

Check Target

Look for target sum (totalSum/2) in stored sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int getTotalSum(struct TreeNode* node) {
    if (!node) return 0;
    return node->val + getTotalSum(node->left) + getTotalSum(node->right);
}

int sums[10000];
int sumCount = 0;

int dfs(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftSum = dfs(node->left);
    int rightSum = dfs(node->right);
    int currentSum = node->val + leftSum + rightSum;
    
    sums[sumCount++] = currentSum;
    return currentSum;
}

bool solution(struct TreeNode* root) {
    if (!root) return false;
    
    int totalSum = getTotalSum(root);
    if (totalSum % 2 != 0) return false;
    
    int target = totalSum / 2;
    sumCount = 0;
    
    dfs(root);
    
    for (int i = 0; i < sumCount - 1; i++) {
        if (sums[i] == target) {
            return true;
        }
    }
    
    return false;
}

int main() {
    struct TreeNode* root = createNode(5);
    root->left = createNode(10);
    root->right = createNode(10);
    root->right->left = createNode(2);
    root->right->right = createNode(3);
    
    bool result = solution(root);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each node visited exactly twice - once to get total sum, once to check subtrees

✓ Linear Growth

Space Complexity

O(n)

Set to store subtree sums plus O(h) recursion stack

⚡ Linearithmic Space

87.5K Views

Medium Frequency

~25 min Avg. Time

891 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler