Children Sum in a Binary Tree

Easy Trees & BST Postorder + Multiple Return Values Original on GeeksforGeeks

Children Sum in a Binary Tree is a easy trees & bst problem solved with the postorder + multiple return values pattern. The best approach, recursive, runs in O(n) time and O(h) space. Below are 2 approaches in Java, from iterative (bfs) up.

Problem

Check whether every non-leaf node’s value equals the sum of its children’s values (a missing child counts as 0). Return 1 if it holds, else 0.

Examples

Example 1

Input: root = [35, 20, 15, 15, 5, 10, 5]
Output: true
Why: 35 = 20 + 15, 20 = 15 + 5, 15 = 10 + 5.

Example 2

Input: root = [1, 4, 3, 5]
Output: false
Why: 4 has one child with value 5.

Constraints

The tree has 1 to 10^5 nodes.
Leaves always satisfy the property; a missing child counts as 0.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Iterative (BFS)	`O(n)`	`O(w)`
Recursive	`O(n)`	`O(h)`

1Iterative (BFS)

TimeO(n)

SpaceO(w)

Visit every non-leaf node with a queue and check that its value equals the sum of its children.

For each polled node with at least one child, compare val with the child sum.

Java

class Solution {
    public static int isSumProperty(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n.left == null && n.right == null) continue;
            int sum = (n.left == null ? 0 : n.left.val) + (n.right == null ? 0 : n.right.val);
            if (sum != n.val) return 0;
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        return 1;
    }
}

2Recursive

TimeO(n)

SpaceO(h)

A leaf (or null) satisfies the property. Otherwise the node's value must equal the children's sum, and both subtrees must satisfy it too.

null or leaf → true.
sum of children == val && check(left) && check(right).

Java

class Solution {
    public static int isSumProperty(TreeNode root) {
        return ok(root) ? 1 : 0;
    }

    private static boolean ok(TreeNode n) {
        if (n == null || (n.left == null && n.right == null)) return true;
        int sum = (n.left == null ? 0 : n.left.val) + (n.right == null ? 0 : n.right.val);
        return sum == n.val && ok(n.left) && ok(n.right);
    }
}

Edge cases to test

Single node
Node with only one child

Hints

Hint 1

Check the node against its children, then check both subtrees.

FAQ

What is the best time complexity for Children Sum in a Binary Tree?

Recursive runs in O(n) time and O(h) extra space.

Which pattern does Children Sum in a Binary Tree use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Largest BST.

Is there a brute force solution for Children Sum in a Binary Tree?

Yes. Iterative (BFS) takes O(n) time and O(w) space. Visit every non-leaf node with a queue and check that its value equals the sum of its children.

Which edge cases should I test for Children Sum in a Binary Tree?

Single node; Node with only one child.