Children Sum Property

Children Sum Property is a classic tree-traversal warm-up. It teaches the single most useful tree habit there is: handle the children before the parent — a post-order walk — and combine their results on the way back up.

The slow way first

A tempting first attempt is to grab one node at a time and, for each, walk down to find its two children and add them. But re-finding children means re-descending the tree, and if you do that from every node you end up touching nodes over and over — wasteful, and easy to get wrong on missing children.

The question to ask: while I am standing on a node, what do I wish I already knew? I wish I already knew that both subtrees below me are valid, and I wish I had each child value right in hand. A single bottom-up pass gives me exactly that.

The idea: check children before the parent

Walk the tree post-order — recurse into the left child, then the right child, then check the current node. By the time we test a node, both subtrees have already been verified. At the node we compute left.val + right.val (treating a missing child as 0) and compare it to the node value. The first node that fails makes the whole answer False.

The key insight: a leaf passes for free, so the only real work happens at internal nodes, and one mismatch anywhere short-circuits the entire tree to False.

Walk through it

Step through the animation. Recursion dives to the leaves first — 3, 5, 2, 1 all pass on their own. Coming back up, node 8 checks out (3 + 5 = 8). Then node 2 is tested: its children sum to 3, but the node holds 2, so it lights up in red. That single failure means the tree does not satisfy the property — even though the root 10 would have matched 8 + 2.

Pseudocode

check(node):
    if node is empty:               # nothing here
        return True
    if node has no children:        # a leaf always passes
        return True
    sum = left child value or 0
        + right child value or 0
    if node value != sum:           # this node breaks the rule
        return False
    return check(left child) and check(right child)

The Python solution

def is_children_sum(node):
    if node is None:
        return True
    if node.left is None and node.right is None:
        return True
    total = (node.left.val if node.left else 0) \
          + (node.right.val if node.right else 0)
    if node.val != total:
        return False
    return is_children_sum(node.left) \
       and is_children_sum(node.right)

• The first base case (line 2) handles an empty subtree — there is nothing to violate, so return True.
• The second base case (line 4) handles a leaf: no children means the rule is trivially satisfied.
• total (lines 6-7) adds the two child values, using 0 for any missing child so the formula always works.
• Line 8 is the heart of the check: if the node value does not equal that sum, this node breaks the property and we return False immediately.
• The final line recurses into both children with and, so any failure deeper in the tree also propagates a False all the way up.

Complexity

We look at each of the n nodes exactly once and do O(1) work per node, so the time is O(n). The only extra space is the recursion stack, which is as deep as the tree height h — O(log n) for a balanced tree, O(n) in the worst case (a degenerate chain).

When this pattern shows up

Practice