Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Children Sum in a Binary Tree

HARDProblemSolveExternal Links

Description

Given the root of a binary tree, determine whether the tree satisfies the Children Sum Property.

The Children Sum Property states that for every non-leaf node in the tree, the node's value must be exactly equal to the sum of the values of its left child and right child. If a child does not exist (is null), its value is treated as 0.

All leaf nodes (nodes with no children) automatically satisfy the property.

Return 1 (true) if every node in the tree satisfies this condition. Return 0 (false) if any node violates it.

Examples

Example 1

Input: root = [35, 20, 15, 15, 5, 10, 5]

       35
      /  \
    20    15
   / \   / \
  15  5 10  5

Output: 1 (True)

Explanation: Every non-leaf node satisfies the property:

  • Node 35: left child (20) + right child (15) = 35 ✓
  • Node 20: left child (15) + right child (5) = 20 ✓
  • Node 15: left child (10) + right child (5) = 15 ✓
  • Leaf nodes 15, 5, 10, 5 have no children, so they are valid by default.

All nodes pass the check, so the answer is 1 (true).

Example 2

Input: root = [1, 4, 3, 5]

     1
    / \
   4   3
  /
 5

Output: 0 (False)

Explanation: The root node has value 1, but the sum of its children is 4 + 3 = 7. Since 1 ≠ 7, the property is violated at the root. Therefore the answer is 0 (false).

Note that node 4 also violates the property: its only child has value 5, but 4 ≠ 5.

Example 3

Input: root = [10, 10]

  10
  /
 10

Output: 1 (True)

Explanation: The root has value 10. Its left child has value 10 and there is no right child (treated as 0). Sum = 10 + 0 = 10. Since 10 = 10, the property holds. The left child (10) is a leaf, which is valid by default.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 0 ≤ node.data ≤ 10^5

Editorial

Brute Force

Intuition

The most direct way to verify the Children Sum Property is to visit every node in the tree and check the rule individually. We can use Breadth-First Search (BFS) — a level-order traversal using a queue — to systematically process each node.

For every node we dequeue, we ask: is this a leaf? If yes, skip it (leaves are always valid). If not, compute the sum of its children's values and compare it to the node's own value. If they don't match, we immediately know the property is violated and can return 0.

Think of it like a school principal inspecting classrooms floor by floor. On each floor (level), they check every classroom (node). If a classroom has students (children), the capacity sign (node value) must match the actual number of students (sum of children). If any classroom fails, the inspection stops and the school fails.

Step-by-Step Explanation

Let's trace through Example 1: root = [35, 20, 15, 15, 5, 10, 5]

       35
      /  \
    20    15
   / \   / \
  15  5 10  5

Step 1: Initialize a queue and enqueue the root node (35).

  • Queue: [35]

Step 2: Dequeue node 35. It has children (not a leaf).

  • Compute children sum: left(20) + right(15) = 35
  • Check: 35 == 35? YES ✓
  • Enqueue children: 20, 15
  • Queue: [20, 15]

Step 3: Dequeue node 20. It has children.

  • Compute children sum: left(15) + right(5) = 20
  • Check: 20 == 20? YES ✓
  • Enqueue children: 15, 5
  • Queue: [15, 15, 5]

Step 4: Dequeue node 15 (right child of root). It has children.

  • Compute children sum: left(10) + right(5) = 15
  • Check: 15 == 15? YES ✓
  • Enqueue children: 10, 5
  • Queue: [15, 5, 10, 5]

Step 5: Dequeue node 15 (leaf). No children → skip.

Step 6: Dequeue node 5 (leaf). No children → skip.

Step 7: Dequeue node 10 (leaf). No children → skip.

Step 8: Dequeue node 5 (leaf). No children → skip. Queue is now empty.

Result: All non-leaf nodes passed the check. Return 1 (true).

BFS Level-Order — Checking Children Sum Property — Watch how we process each node level by level using a queue, verifying that every non-leaf node's value equals the sum of its children.

Algorithm

  1. If the root is null, return 1 (an empty tree trivially satisfies the property)
  2. Create a queue and enqueue the root
  3. While the queue is not empty:
    a. Dequeue the front node as curr
    b. If curr is a leaf (both children are null), skip to the next iteration
    c. Compute childSum = 0
    d. If curr.left exists, add curr.left.data to childSum and enqueue curr.left
    e. If curr.right exists, add curr.right.data to childSum and enqueue curr.right
    f. If curr.data ≠ childSum, return 0 (property violated)
  4. Return 1 (all nodes passed)

Code

class Solution {
public:
    int isSumProperty(Node* root) {
        if (root == nullptr) return 1;

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* curr = q.front();
            q.pop();

            // Leaf nodes are always valid
            if (curr->left == nullptr && curr->right == nullptr)
                continue;

            int childSum = 0;
            if (curr->left != nullptr) {
                childSum += curr->left->data;
                q.push(curr->left);
            }
            if (curr->right != nullptr) {
                childSum += curr->right->data;
                q.push(curr->right);
            }

            if (curr->data != childSum)
                return 0;
        }
        return 1;
    }
};
from collections import deque

class Solution:
    def isSumProperty(self, root):
        if root is None:
            return 1

        q = deque([root])

        while q:
            curr = q.popleft()

            # Leaf nodes are always valid
            if curr.left is None and curr.right is None:
                continue

            child_sum = 0
            if curr.left:
                child_sum += curr.left.data
                q.append(curr.left)
            if curr.right:
                child_sum += curr.right.data
                q.append(curr.right)

            if curr.data != child_sum:
                return 0

        return 1
class Solution {
    public static int isSumProperty(Node root) {
        if (root == null) return 1;

        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            Node curr = q.poll();

            // Leaf nodes are always valid
            if (curr.left == null && curr.right == null)
                continue;

            int childSum = 0;
            if (curr.left != null) {
                childSum += curr.left.data;
                q.add(curr.left);
            }
            if (curr.right != null) {
                childSum += curr.right.data;
                q.add(curr.right);
            }

            if (curr.data != childSum)
                return 0;
        }
        return 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once via the queue. For each node, the check (sum computation and comparison) takes O(1) time. Total: O(n).

Space Complexity: O(n)

The queue can hold up to O(n) nodes in the worst case. In a complete binary tree, the last level can have up to n/2 nodes, all of which would be in the queue simultaneously. Therefore the space used by the queue is O(n).

Why This Approach Is Not Efficient

While the BFS approach works correctly in O(n) time, its space usage is suboptimal. The queue stores nodes at the current level plus the next level, which in a complete binary tree means up to n/2 nodes at the widest level. For trees with up to 10^5 nodes, this queue can consume significant memory.

The core issue is that BFS processes the tree breadth-wise, which requires remembering all nodes at the current frontier. But we don't actually need to process nodes in level order — we just need to visit every node and check a local property.

If we switch to Depth-First Search (DFS) using recursion, the space usage drops to O(h), where h is the height of the tree. For a balanced tree with 10^5 nodes, h ≈ 17 (log₂ of 10^5), which is dramatically less than the n/2 ≈ 50,000 nodes a BFS queue might hold. Even in the worst case (a skewed tree where h = n), DFS uses at most as much space as BFS.

Optimal Approach - Recursive DFS

Intuition

Instead of using an explicit queue to track which nodes to visit next, we can leverage the call stack through recursion. DFS naturally explores one branch deeply before moving to the next, which means the maximum memory used at any time is proportional to the tree's height, not its width.

The recursive approach is elegant in its simplicity:

  1. If the current node is null or a leaf, it's automatically valid — return 1.
  2. Otherwise, compute the sum of the children's values.
  3. If the node's value doesn't match this sum, the property fails — return 0.
  4. Otherwise, recursively check both the left and right subtrees.
  5. The tree satisfies the property only if the current node passes AND both subtrees recursively pass.

Think of it like a chain of trust: a manager (parent node) is trustworthy only if their reported headcount (node value) matches the actual headcount of their direct reports (children values), AND each of those direct reports is also trustworthy in the same way. One dishonest node anywhere in the hierarchy breaks the entire chain.

Step-by-Step Explanation

Let's trace the recursive DFS through Example 1:

       35
      /  \
    20    15
   / \   / \
  15  5 10  5

Step 1: Call isSumProperty(35). Node 35 is not null, not a leaf.

  • Children sum = 20 + 15 = 35. Check: 35 == 35? YES ✓
  • Recurse into left subtree.

Step 2: Call isSumProperty(20). Node 20 is not null, not a leaf.

  • Children sum = 15 + 5 = 20. Check: 20 == 20? YES ✓
  • Recurse into left subtree.

Step 3: Call isSumProperty(15). Node 15 is a leaf (no children).

  • Leaf nodes are automatically valid. Return 1.

Step 4: Back at node 20. Left subtree passed. Recurse into right subtree.

  • Call isSumProperty(5). Node 5 is a leaf. Return 1.

Step 5: Back at node 20. Both subtrees passed. Node 20 itself passed. Return 1.

Step 6: Back at node 35. Left subtree passed. Recurse into right subtree.

  • Call isSumProperty(15) (right child of root). Not a leaf.
  • Children sum = 10 + 5 = 15. Check: 15 == 15? YES ✓
  • Recurse into left subtree.

Step 7: Call isSumProperty(10). Leaf node. Return 1.

Step 8: Back at node 15. Left subtree passed. Recurse into right subtree.

  • Call isSumProperty(5). Leaf node. Return 1.

Step 9: Back at node 15. Both subtrees passed. Node 15 itself passed. Return 1.

Step 10: Back at root 35. Both subtrees passed. Root itself passed. Return 1.

Result: The entire tree satisfies the Children Sum Property. Return 1 (true).

Recursive DFS — Depth-First Children Sum Verification — Watch how DFS dives deep into the left subtree first, verifying each node's children sum on the way, then backtracks and checks the right subtree.

Algorithm

  1. Base cases:
    • If the node is null, return 1 (nothing to check)
    • If the node is a leaf (both children are null), return 1 (leaves are always valid)
  2. Compute childSum = 0
    • If the left child exists, add its value to childSum
    • If the right child exists, add its value to childSum
  3. If node.data ≠ childSum, return 0 (property violated at this node)
  4. Recursively check the left subtree: leftResult = isSumProperty(node.left)
  5. Recursively check the right subtree: rightResult = isSumProperty(node.right)
  6. Return 1 only if both leftResult and rightResult are 1, otherwise return 0

Code

class Solution {
public:
    int isSumProperty(Node* root) {
        // Base cases: null or leaf
        if (root == nullptr)
            return 1;
        if (root->left == nullptr && root->right == nullptr)
            return 1;

        // Compute sum of children values
        int childSum = 0;
        if (root->left != nullptr)
            childSum += root->left->data;
        if (root->right != nullptr)
            childSum += root->right->data;

        // Check current node
        if (root->data != childSum)
            return 0;

        // Recursively verify both subtrees
        if (isSumProperty(root->left) == 0)
            return 0;
        if (isSumProperty(root->right) == 0)
            return 0;

        return 1;
    }
};
class Solution:
    def isSumProperty(self, root):
        # Base cases: null or leaf
        if root is None:
            return 1
        if root.left is None and root.right is None:
            return 1

        # Compute sum of children values
        child_sum = 0
        if root.left:
            child_sum += root.left.data
        if root.right:
            child_sum += root.right.data

        # Check current node
        if root.data != child_sum:
            return 0

        # Recursively verify both subtrees
        if not self.isSumProperty(root.left):
            return 0
        if not self.isSumProperty(root.right):
            return 0

        return 1
class Solution {
    public static int isSumProperty(Node root) {
        // Base cases: null or leaf
        if (root == null)
            return 1;
        if (root.left == null && root.right == null)
            return 1;

        // Compute sum of children values
        int childSum = 0;
        if (root.left != null)
            childSum += root.left.data;
        if (root.right != null)
            childSum += root.right.data;

        // Check current node
        if (root.data != childSum)
            return 0;

        // Recursively verify both subtrees
        if (isSumProperty(root.left) == 0)
            return 0;
        if (isSumProperty(root.right) == 0)
            return 0;

        return 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once. At each node, we perform a constant amount of work: checking if it's a leaf, computing the children sum (at most two additions), and making a comparison. Total: O(n).

Space Complexity: O(h), where h is the height of the tree

The recursion uses call stack space proportional to the maximum depth of the tree. For a balanced binary tree with n nodes, h = O(log n). For example, with n = 100,000 nodes, a balanced tree has height ≈ 17, using only 17 stack frames instead of the thousands of queue entries BFS might need.

In the worst case — a completely skewed tree (essentially a linked list) — h = n, so space is O(n). However, for most practical inputs (especially balanced or near-balanced trees), the recursive approach is significantly more memory-efficient than the BFS approach.

Since no algorithm can avoid visiting all n nodes (we must check every internal node), O(n) time is optimal. The O(h) space is also optimal for a recursive solution — the only way to achieve O(1) space would be Morris Traversal, which is unnecessary for this simple property-checking problem.