Binary Tree Children Sum Property

Description

A tree has the children sum property when every node's value equals the sum of its children's values. Leaves are exempt, since they have no children. Two tasks come with it. Checking whether a tree already has the property is one read-only pass. Repairing a tree that doesn't, by only ever increasing values, takes a walk down and a walk back up.

We'll go from simple to more technical:

1. The pattern: the repair - push down, recurse, sum up.
2. A second flavor: the read-only check.
3. Where rollup rules like this hold in production.
4. The mistakes: skipping the upward pass, writing to missing children, and leaves.

The approach (repairing a tree)

You may only increase values. So when a node is bigger than its children's sum, you can't lower it. Instead, raise a child to the node's value and let the fix carry on below. When a node's children already add up to at least its value, the node simply takes their sum. Then, after both subtrees are repaired, set each node to its children's sum on the way back up. That last step matters, because a change deep down can make every ancestor wrong.

Here's a tree before and after the repair:

Without steps 4 and 5, the root would still say 20 while its children add up to 28.

void changeTree(TreeNode root) {
    if (root == null) return;
    int childSum = (root.left != null ? root.left.val : 0) + (root.right != null ? root.right.val : 0);
    if (childSum >= root.val) {
        root.val = childSum;                          // children already dominate - adopt their sum
    } else if (root.left != null) {
        root.left.val = root.val;                       // push the excess down onto whichever child exists
    } else if (root.right != null) {
        root.right.val = root.val;
    }
    changeTree(root.left);
    changeTree(root.right);
    // bottom-up: re-derive this node's value now that its children are finalized
    int total = (root.left != null ? root.left.val : 0) + (root.right != null ? root.right.val : 0);
    if (root.left != null || root.right != null) root.val = total;
}

def change_tree(root: TreeNode | None) -> None:
    if root is None:
        return
    child_sum = (root.left.val if root.left else 0) + (root.right.val if root.right else 0)
    if child_sum >= root.val:
        root.val = child_sum               # children already dominate - adopt their sum
    elif root.left:
        root.left.val = root.val           # push the excess down onto whichever child exists
    elif root.right:
        root.right.val = root.val
    change_tree(root.left)
    change_tree(root.right)
    # bottom-up: re-derive this node's value now that its children are finalized
    if root.left or root.right:
        root.val = (root.left.val if root.left else 0) + (root.right.val if root.right else 0)

A second flavor: checking without changing anything

Checking whether a tree already has the property is much simpler. There's no pushing and no second pass. Each node compares its value with its children's sum, and every subtree must pass too. In the example, the "After" tree passes and the "Before" tree fails at the root.

boolean checkChildrenSumProperty(TreeNode node) {
    if (node == null) return true;
    if (node.left == null && node.right == null) return true;   // a leaf trivially satisfies it
    int childSum = (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0);
    return node.val == childSum
        && checkChildrenSumProperty(node.left)
        && checkChildrenSumProperty(node.right);
}

def check_children_sum_property(node: TreeNode | None) -> bool:
    if node is None:
        return True
    if node.left is None and node.right is None:
        return True                        # a leaf trivially satisfies it
    child_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
    return (node.val == child_sum
            and check_children_sum_property(node.left)
            and check_children_sum_property(node.right))

The leaf check is what makes this correct. A leaf's children sum to 0. Without the check, every leaf would have to hold 0 to pass.

Where you'll see it

Budgets and ledgers often follow this rule: a department's budget is the sum of its teams' budgets. When someone edits a team's number, every total above it has to be recomputed, bottom up. Auditing whether the totals already add up is the simpler check.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A repair pushes a node's value down to a child and never comes back to that node. What goes wrong?

2. A repair writes root.left.val = root.val without checking that root.left exists. What happens on a node with only a right child?

3. A check computes the children's sum as 0 for leaves and compares it with the leaf's value. What does it report for a correct tree?

Key takeaways

• The repair has two parts: push values down on the way in, then set each node to its children's sum on the way back up.
• The upward pass isn't optional. A deep change only reaches the ancestors through it.
• A node with one child pushes onto that child, never onto a missing one.
• The read-only check is one pass with no changes, but it needs an explicit leaf case.