Equal Tree Partition

medium dfs tree

Problem

Can we remove one edge to split the tree into two with equal sum?

Inputtree=[5,10,10,null,null,2,3]

OutputTrue

Cut edge between 5 and right child → 5+10=15 each.

input

def check_equal_tree(root):
    sums = []
    def dfs(n):
        if not n: return 0
        s = n.val + dfs(n.left) + dfs(n.right); sums.append(s); return s
    total = dfs(root); sums.pop()
    return total % 2 == 0 and total // 2 in sums

function checkEqualTree(root) {
  const sums = [];
  const dfs = n => { if (!n) return 0; const s = n.val + dfs(n.left) + dfs(n.right); sums.push(s); return s; };
  const total = dfs(root); sums.pop();
  return total % 2 === 0 && sums.includes(total / 2);
}

boolean checkEqualTree(TreeNode root) {
    List sums = new ArrayList<>();
    int total = dfs(root, sums); sums.remove(sums.size() - 1);
    return total % 2 == 0 && sums.contains(total / 2);
}
int dfs(TreeNode n, List sums) {
    if (n == null) return 0;
    int s = n.val + dfs(n.left, sums) + dfs(n.right, sums); sums.add(s); return s;
}

int dfs(TreeNode* n, vector& s) { if (!n) return 0; int v = n->val + dfs(n->left, s) + dfs(n->right, s); s.push_back(v); return v; }
bool checkEqualTree(TreeNode* root) {
    vector s; int total = dfs(root, s); s.pop_back();
    return total % 2 == 0 && find(s.begin(), s.end(), total / 2) != s.end();
}

Explanation

We want to cut exactly one edge so the tree splits into two halves with the same sum. If you cut the edge above some subtree, the two pieces are that subtree and everything else. For them to be equal, the subtree's sum must be exactly half of the whole tree's total.

So the plan is: compute the sum of every subtree and stash all of them in a list. A post-order DFS does this in one sweep — dfs(n) returns n.val + dfs(left) + dfs(right) and pushes that value onto sums before returning.

The very last value added is the total of the whole tree, which we discard with sums.pop() — we can't cut above the root, so the full-tree sum isn't a valid half.

Finally we check two things: the total must be even (an odd total can never split evenly), and total / 2 must appear among the remaining subtree sums. If both hold, such a cut exists.

Example: [5,10,10,null,null,2,3]. The total is 30, half is 15, and the right subtree 10 + 2 + 3 sums to 15, so the answer is True.

Time: O(n) Space: O(n)