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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Iterative (BFS)O(n)O(w)
RecursiveO(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.

  1. For each polled node with at least one child, compare val with the child sum.
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.

  1. null or leaf → true.
  2. sum of children == val && check(left) && check(right).
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.