Children Sum Parent

Problem Link

Children Sum Parent – GeeksforGeeks

Problem: Children Sum Parent

Problem Statement

Given a binary tree, write a function that returns true if the tree follows the children sum property, else return false.

Children Sum Property:
For every node of the tree, the value of the node must be equal to the sum of the values of its left and right child.
For leaves, this condition is vacuously true.

Examples

Example 1:

        10
       /  \
      8    2
     / \
    3   5

Output: true
Explanation: 8 = 3 + 5 and 10 = 8 + 2

Example 2:

       10
      /  \
     20   30

Output: false
Explanation: 10 ≠ 20 + 30

Constraints

• 1 <= Number of nodes <= 10⁵

• 0 <= Data of a node <= 10⁶

Intuition

The condition must be verified recursively at each node:

• If the node is null or a leaf, return true.

• Otherwise, check:

  • node.data == left.data + right.data

  • Recursively verify the same property for left and right subtrees.

Approach

1. Use post-order traversal (check children first).

2. For each node:

   • If node is null or a leaf → return true

   • Recursively check left and right subtrees

   • If both pass, check if the current node's value equals the sum of child values.

Code (Java)

class Solution {
    public static int isSumProperty(Node root) {
        return check(root) ? 1 : 0;
    }

    private static boolean check(Node node) {
        if (node == null || (node.left == null && node.right == null)) {
            return true;
        }

        int leftVal = (node.left != null) ? node.left.data : 0;
        int rightVal = (node.right != null) ? node.right.data : 0;

        boolean currentNodeCheck = (node.data == leftVal + rightVal);
        return currentNodeCheck && check(node.left) && check(node.right);
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is visited once.

• Space Complexity: O(H)
  Where H is the height of the tree (due to recursion stack). Worst case: O(N) for skewed tree.

Dry Run

Input Tree:

        10
       /  \
      8    2
     / \
    3   5

• Node 3 and 5 → leaves → valid

• Node 8 = 3 + 5 → valid

• Node 2 → leaf → valid

• Node 10 = 8 + 2 → valid

Result: true

Conclusion

• This is a simple recursive tree check problem using a bottom-up approach.

• A good example of using postorder traversal to validate local constraints at each node after verifying subtrees.

• Frequently asked in tree traversal-based interviews for verifying invariants.