Children Sum in a Binary Tree
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
1to10^5nodes. - 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Iterative (BFS) | O(n) | O(w) |
| Recursive | O(n) | O(h) |
1Iterative (BFS)
O(n)O(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.
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;
}
}class Solution:
def isSumProperty(self, root: Optional[TreeNode]) -> int:
q = deque([root])
while q:
n = q.popleft()
if n.left is None and n.right is None:
continue
total = (0 if n.left is None else n.left.val) + (0 if n.right is None else n.right.val)
if total != n.val:
return 0
if n.left is not None:
q.append(n.left)
if n.right is not None:
q.append(n.right)
return 1class Solution {
public:
static int isSumProperty(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* n = q.front(); q.pop();
if (n->left == nullptr && n->right == nullptr) continue;
int sum = (n->left == nullptr ? 0 : n->left->val) + (n->right == nullptr ? 0 : n->right->val);
if (sum != n->val) return 0;
if (n->left != nullptr) q.push(n->left);
if (n->right != nullptr) q.push(n->right);
}
return 1;
}
};function isSumProperty(root) {
const q = [root];
let head = 0;
while (head < q.length) {
const n = q[head++];
if (n.left === null && n.right === null) continue;
const 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.push(n.left);
if (n.right !== null) q.push(n.right);
}
return 1;
}2Recursive
O(n)O(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).
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);
}
}class Solution:
def isSumProperty(self, root: Optional[TreeNode]) -> int:
return 1 if self.ok(root) else 0
def ok(self, n: Optional[TreeNode]) -> bool:
if n is None or (n.left is None and n.right is None):
return True
total = (0 if n.left is None else n.left.val) + (0 if n.right is None else n.right.val)
return total == n.val and self.ok(n.left) and self.ok(n.right)class Solution {
public:
static int isSumProperty(TreeNode* root) {
return ok(root) ? 1 : 0;
}
private:
static bool ok(TreeNode* n) {
if (n == nullptr || (n->left == nullptr && n->right == nullptr)) return true;
int sum = (n->left == nullptr ? 0 : n->left->val) + (n->right == nullptr ? 0 : n->right->val);
return sum == n->val && ok(n->left) && ok(n->right);
}
};function isSumProperty(root) {
return ok(root) ? 1 : 0;
}
function ok(n) {
if (n === null || (n.left === null && n.right === null)) return true;
const 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.