Does Every Node Equal the Sum of Its Children
Solve this ProblemYou are given the root of a binary tree of integers. The tree has the children-sum property if every node that has at least one child holds a value equal to the sum of the values of its children, where a missing child counts as 0. Leaves are not checked. Return true if the property holds at every node, and false otherwise. An empty tree satisfies the property.
A level-order sweep with a queue checks every node in turn. A recursion checks the same thing while stopping at the first violation and using only the call stack.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
The tree has the children-sum property when every node that has at least one child holds a value equal to the sum of its children's values (a missing child counts as 0). Leaves are never checked. Return true if the property holds at every node, false otherwise; an empty tree qualifies
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Level-by-Level Sweep With a Queue
GoodVisit every node in level order with a queue. A leaf is skipped. For any other node, add up the values of the children that exist (a missing child adds nothing) and compare with the node's own value: on a mismatch the property fails, so return false; otherwise queue the children. If the queue runs empty without a mismatch, the property holds at every node. O(n) time; the queue can hold a whole level, so O(w) space.
O(n)O(w)1class Solution {
2 public boolean childrenAddUp(TreeNode root) {
3 if (root == null) return true;
4 Queue<TreeNode> queue = new ArrayDeque<>();
5 queue.add(root);
6 while (!queue.isEmpty()) {
7 TreeNode node = queue.poll();
8 if (node.left == null && node.right == null) continue;
9 int sum = 0;
10 if (node.left != null) sum += node.left.val;
11 if (node.right != null) sum += node.right.val;
12 if (node.val != sum) return false;
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 return true;
17 }
18}Optimal — Recursive Check That Stops at the First Violation
OptimalDo the same check recursively: an empty tree and a leaf both pass; for any other node compare its value with the sum of its existing children; if it differs, fail at once; otherwise the property must also hold for the left subtree AND the right subtree. The && short-circuits: after a failure nothing else is examined, and a success on the left is followed by the right. It uses only the recursion stack (O(h), which is small for balanced trees) instead of a queue that can hold a whole level. O(n) time in the worst case.
O(n)O(h)1class Solution {
2 public boolean childrenAddUp(TreeNode root) {
3 if (root == null) return true;
4 if (root.left == null && root.right == null) return true;
5 int sum = 0;
6 if (root.left != null) sum += root.left.val;
7 if (root.right != null) sum += root.right.val;
8 if (root.val != sum) return false;
9 return childrenAddUp(root.left) && childrenAddUp(root.right);
10 }
11}