L29: Children Sum Property in Binary Tree | $O(N)$ Approach

This chapter explores the algorithmic strategy for solving the Children Sum Property problem in a binary tree. We will examine how to transform an arbitrary binary tree so that it satisfies the children sum invariant in linear time, $O(N)$, using a clever top-down and bottom-up traversal technique.

1. Problem Statement & The Children Sum Invariant

The Children Sum Property is a structural invariant defined for binary trees.

• The Rule: For every node in the binary tree, the value of the node must be exactly equal to the sum of its left child's value and its right child's value.

• Leaf Nodes: Leaf nodes naturally satisfy this condition (or are exempt since they have no children, though standard convention treats them as valid or handles them as base cases).
• Allowed Modifications: You are given a binary tree that does not initially satisfy this property. You are permitted to increment node values by $+1$ as many times as you want. However, you cannot decrement any node values, and you cannot change the structural topology of the tree (no adding or removing nodes).

2. Core Mental Model: Why Simple Increments Are Tricky

At first glance, the problem might appear trivial: if a parent's value is less than the sum of its children, just increment the parent. But what if the parent's value is greater than the sum of its children?

Real-Life Analogy: Balancing a Budget

Imagine balancing a budget where individual department allocations (children) must sum up exactly to the total corporate pool (parent). If the corporate pool is smaller than the sum of the departments, you can easily pump more money into the corporate pool. But if the corporate pool is already larger than the sum of its departments, simply increasing the parent breaks downward consistency. If you instead try to increase the children's budgets to match a large parent, you ripple changes down the entire subtree, potentially causing cascading imbalances below.

The Naive Trap

If you attempt to fix imbalances locally from the bottom up, changing a child's value to fix a parent can invalidate that child's relationship with its own children further down.

• Naive Approach Complexity: Attempting to fix this with uncoordinated local increments leads to an inefficient $O(N^2)$ time complexity because fixing a lower level can repeatedly invalidate upper levels.
• Goal: We need an approach that achieves this in a single traversal with $O(N)$ time complexity.

3. The Intuitive Solution: Top-Down vs. Bottom-Up Strategy

To solve this in $O(N)$, we must use a two-phase philosophy during a single recursive tree traversal:

1. While Going Down (Pre-Order Phase): Push large values down into the children. If a parent's value is greater than the sum of its children, force the children's sum up to match the parent by inflating the children's values. If the children's sum is already greater, inflate the parent.
2. While Coming Back Up (Post-Order Phase): Recalculate and update the parent's value to be the exact sum of its updated children.

Why This Works

By artificially inflating node values on the way down, we ensure that when we process nodes on the way back up, the children's values are guaranteed to be greater than or equal to the original parent's value. Thus, updating the parent to equal left + right will never cause a downward shortage.

4. Step-by-Step Flow Walkthrough

Let's trace how the algorithm executes on a node during recursion:

5. Algorithm Code Implementations

Below are the complete C++ and Java implementations demonstrating this $O(N)$ single-pass strategy.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

class Solution {
public:
    void changeChildrenSum(Node* root) {
        // Base case: if root is null, return
        if (root == NULL) return;
        
        int childSum = 0;
        if (root->left) childSum += root->left->data;
        if (root->right) childSum += root->right->data;
        
        // If children sum is greater than or equal to root, update root
        if (childSum >= root->data) {
            root->data = childSum;
        } 
        // If root is greater than children sum, push root's value down to children
        else {
            if (root->left) root->left->data = root->data;
            if (root->right) root->right->data = root->data;
        }
        
        // Traverse down to left and right children
        changeChildrenSum(root->left);
        changeChildrenSum(root->right);
        
        // Coming back up (Post-order phase): Recompute total sum of children
        int tot = 0;
        if (root->left) tot += root->left->data;
        if (root->right) tot += root->right->data;
        
        // If it's not a leaf node, update the current node with the new child sum
        if (root->left || root->right) {
            root->data = tot;
        }
    }
};

Java Implementation

// Definition for a binary tree node.
class Node {
    int data;
    Node left, right;
    
    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    public void changeChildrenSum(Node root) {
        // Base case
        if (root == null) return;
        
        int childSum = 0;
        if (root.left != null) childSum += root.left.data;
        if (root.right != null) childSum += root.right.data;
        
        // Top-down adjustment
        if (childSum >= root.data) {
            root.data = childSum;
        } else {
            if (root.left != null) root.left.data = root.data;
            if (root.right != null) root.right.data = root.data;
        }
        
        // Recursive calls
        changeChildrenSum(root.left);
        changeChildrenSum(root.right);
        
        // Bottom-up consolidation
        int tot = 0;
        if (root.left != null) tot += root.left.data;
        if (root.right != null) tot += root.right.data;
        
        if (root.left != null || root.right != null) {
            root.data = tot;
        }
    }
}

6. Complexity Analysis

7. Summary and Key Takeaways

• Problem Objective: Transform any binary tree to satisfy the Children Sum Property ($\text{Node} = \text{Left} + \text{Right}$) using only increments ($+1$) without changing tree structure.
• The Inefficiency of Naive Approaches: Naive bottom-up approaches lead to $O(N^2)$ time complexity due to cascading invalidations across tree levels.
• The Single-Traversal Secret: Combine a Pre-order downward adjustment with a Post-order upward consolidation.
• Downward Phase Strategy: If a parent is larger than its children, push the parent's value down to the children so child values become artificially inflated.
• Upward Phase Strategy: On the way back up from recursion, assign the exact sum of the children to the parent node.
• Guaranteed Correctness: Inflating values on the way down guarantees that the children's sum will never fall short when updating parents on the way back up.
• Optimal Efficiency: Achieves a clean linear time complexity of $O(N)$ with a single recursive DFS pass.