Children Sum in a Binary Tree

Easy
1892.

Children Sum in a Binary Tree

Children Sum in a Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Microsoft and Samsung interviews.

A binary tree has the children sum property if, for every node that has at least one child, the node's value equals the sum of its children's values. A missing child counts as 0, and leaves satisfy the property automatically.

Given the root of a binary tree, return true if every node satisfies the property, and false otherwise.

Example 1

Input
root = [35,20,15,15,5,10,5]
Output
true
Explanation
20 = 15 + 5, 15 = 10 + 5 and 35 = 20 + 15; leaves need no check.

Example 2

Input
root = [1,4,3,5]
Output
false
Explanation
4 has the single child 5, and 4 ≠ 5 (the root fails too: 1 ≠ 4 + 3).

Example 3

Input
root = [10,10]
Output
true
Explanation
A missing child counts as 0: 10 = 10 + 0.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSumProperty = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Children Sum in a Binary Tree — Problem & Solution

Children Sum in a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Children Sum in a Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Microsoft and Samsung interviews.

Problem statement

A binary tree has the children sum property if, for every node that has at least one child, the node's value equals the sum of its children's values. A missing child counts as 0, and leaves satisfy the property automatically.

Given the root of a binary tree, return true if every node satisfies the property, and false otherwise.

Example 1

Input: root = [35,20,15,15,5,10,5]
Output: true
Explanation: 20 = 15 + 5, 15 = 10 + 5 and 35 = 20 + 15; leaves need no check.

Example 2

Input: root = [1,4,3,5]
Output: false
Explanation: 4 has the single child 5, and 4 ≠ 5 (the root fails too: 1 ≠ 4 + 3).

Example 3

Input: root = [10,10]
Output: true
Explanation: A missing child counts as 0: 10 = 10 + 0.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5

Hints for Children Sum in a Binary Tree

  1. Hint 1

    The property is local: each node only needs its own value and its children's values.

  2. Hint 2

    Skip leaves; for any other node add up the children that exist and compare.

  3. Hint 3

    Visit every node (any traversal) and stop at the first one that fails.

How to solve Children Sum in a Binary Tree

The condition involves a node and its direct children only, so checking it at every non-leaf node during one traversal decides the whole tree.

Approach

  1. Traverse the tree.
  2. At a leaf, do nothing.
  3. At any other node, compute sum = left child's value (or 0) + right child's value (or 0); if sum != node.val, return false.
  4. If the traversal finishes, return true.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion or stack

Pitfalls

  • A node with one child must equal that child's value alone — the missing child adds 0.
  • Leaves have no children to sum; do not require them to be 0.

Reference solution

Python

from typing import Optional

def isSumProperty(root: Optional[TreeNode]) -> bool:
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        if node.left is None and node.right is None:
            continue
        total = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
        if total != node.val:
            return False
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return True

Java

public static boolean isSumProperty(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) return true;
    int total = (root.left != null ? root.left.val : 0) + (root.right != null ? root.right.val : 0);
    return total == root.val && isSumProperty(root.left) && isSumProperty(root.right);
}

C++

bool isSumProperty(TreeNode* root) {
    if (!root || (!root->left && !root->right)) return true;
    int total = (root->left ? root->left->val : 0) + (root->right ? root->right->val : 0);
    return total == root->val && isSumProperty(root->left) && isSumProperty(root->right);
}

JavaScript

var isSumProperty = function(root) {
    var stack = root === null ? [] : [root];
    while (stack.length > 0) {
        var node = stack.pop();
        if (node.left === null && node.right === null) continue;
        var total = (node.left !== null ? node.left.val : 0) + (node.right !== null ? node.right.val : 0);
        if (total !== node.val) return false;
        if (node.left !== null) stack.push(node.left);
        if (node.right !== null) stack.push(node.right);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals