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.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Microsoft, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^51 <= Node.val <= 10^5
Hints for Children Sum in a Binary Tree
Hint 1
The property is local: each node only needs its own value and its children's values.
Hint 2
Skip leaves; for any other node add up the children that exist and compare.
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
- Traverse the tree.
- At a leaf, do nothing.
- At any other node, compute
sum= left child's value (or 0) + right child's value (or 0); ifsum != node.val, returnfalse. - 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 TrueJava
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