Children Sum Property in Binary Tree

Medium TUF ID 185 A2ZSDE

Problem

A binary tree has the children sum property when every node that has at least one child is equal to the sum of its children’s values; a missing child counts as 0, and leaves have nothing to satisfy. This row covers two tasks:

Check whether a given tree has the property.
Convert a tree so that it has the property. You may increase any node’s value by any amount, as often as you like, but you may never decrease a value and you may not change the shape. Any tree that satisfies these rules is accepted. This is the version taught in Striver’s sheet.

Values are non-negative integers. Without the “only increase” rule the conversion would be trivial (set everything to 0), so that rule is the whole difficulty.

Example 1 (check)

        10
       /  \
      8    2
     / \   /
    3   5 2

answer = true

10 = 8 + 2, 8 = 3 + 5, and 2 = 2 (one child, the missing one counts as 0).

Example 2 (convert)

input                 one valid output       another valid output
        50                   200                     50
      /    \               /     \                 /    \
     7      2            100     100             19      31
    / \    / \           / \     / \             / \    / \
   3   5  1  30         50 50   50  50          14  5  1   30

Both outputs satisfy the property, keep the shape, and never lower a value. The middle one comes from the optimal approach below, the right one from the brute-force approach.

Checking the property

Intuition. The property is local: each node only has to agree with its own children. So a recursion that checks the current node and then both subtrees is enough, and the && stops at the first violation.

static boolean satisfies(TreeNode node) {
    if (node == null || (node.left == null && node.right == null)) return true;   // leaves have nothing to match
    int sum = (node.left == null ? 0 : node.left.val) + (node.right == null ? 0 : node.right.val);
    return node.val == sum && satisfies(node.left) && satisfies(node.right);
}

Complexity. Time O(n), space O(h) for the recursion, where h is the height.

Approach 1: Brute force, fix bottom-up and push surpluses down

Intuition. Fix the tree from the bottom. Process both subtrees first (post-order), so they already satisfy the property. Now compare the node with its children’s sum:

Sum too big. Raise the node to the sum. That is allowed and fixes this node.
Sum too small. We cannot lower the node, so we must raise a child by the difference diff. But that child was balanced, and now it exceeds its own children’s sum by diff. So raise one of its children by diff as well, and so on down a single path until we reach a leaf, which has nothing to satisfy. Every node on that path ends up raised by the same diff, so each one is balanced again.

Algorithm.

If the node is empty or a leaf, return.
Convert the left and right subtrees.
Let sum be the children’s sum. If sum > node.val, set node.val = sum.
If sum < node.val, walk down one path from a child to a leaf, adding node.val - sum to every node on it.

static void bruteForce(TreeNode node) {
    if (node == null || (node.left == null && node.right == null)) return;
    bruteForce(node.left);                                    // both subtrees already satisfy the property
    bruteForce(node.right);
    int sum = (node.left == null ? 0 : node.left.val) + (node.right == null ? 0 : node.right.val);
    if (sum > node.val) node.val = sum;                       // raise the parent
    else if (sum < node.val) pushDown(node, node.val - sum);  // raise a child instead, and repair below it
}

static void pushDown(TreeNode node, int diff) {
    TreeNode child = node.left != null ? node.left : node.right;
    while (child != null) {                                   // walk one path down to a leaf
        child.val += diff;                                    // each raised node needs one raised child below it
        child = child.left != null ? child.left : child.right;
    }
}

Complexity. Time O(n * h): in the worst case every node pushes a surplus down a path of length h, which is O(n^2) for a skewed tree. Space O(h) for the recursion.

Approach 2: Optimal, raise children on the way down

Intuition. The brute force is slow because surpluses are discovered late, after the subtree below is already built, and then have to be pushed back down. Striver’s trick is to push them down before building the subtree, while it is still cheap:

On the way down, look at the node and its children. If the children’s sum is already at least the node, raise the node to that sum. Otherwise set each child to the node’s value. Either way, after this step the node is no larger than the sum of its children. Each child is only raised: when the sum is smaller than the node, every individual child is smaller still.
Recurse into both children.
On the way up, set the node to the sum of its children (if it has any).

Why does the final step never lower a node? Values only ever increase during a call (by induction on the subtree), and after the downward step the children’s sum was already at least the node. So the sum after the recursion is at least that large too.

Why does the result satisfy the property? Each node’s value is fixed for good when its own call returns: its parent only changes it before the call, and its own last action sets it to its children’s final sum. So every non-leaf ends up equal to the sum of its children’s final values.

Algorithm.

If the node is empty, return.
childSum = sum of the children’s values. If childSum >= node.val, set node.val = childSum; otherwise set each existing child to node.val.
Recurse into the left and right child.
If the node has a child, set node.val to the sum of its children.

static void optimal(TreeNode node) {
    if (node == null) return;
    int childSum = (node.left == null ? 0 : node.left.val) + (node.right == null ? 0 : node.right.val);
    if (childSum >= node.val) {
        node.val = childSum;                                  // children already cover the parent
    } else {
        if (node.left != null) node.left.val = node.val;      // lift each child to the parent's value
        if (node.right != null) node.right.val = node.val;
    }
    optimal(node.left);
    optimal(node.right);
    if (node.left != null || node.right != null) {            // a leaf keeps its value
        node.val = (node.left == null ? 0 : node.left.val) + (node.right == null ? 0 : node.right.val);
    }
}

Dry run on Example 2:

step	node	action	values afterwards
down	50	children sum 9 < 50, lift children	7 becomes 50, 2 becomes 50
down	left 50	children sum 8 < 50, lift children	3 becomes 50, 5 becomes 50
leaves	50, 50	nothing to do
up	left	50 + 50	left becomes 100
down	right 50	children sum 31 < 50, lift children	1 becomes 50, 30 becomes 50
up	right	50 + 50	right becomes 100
up	root	100 + 100	root becomes 200

Complexity. Time O(n): each node does constant work twice, once on the way down and once on the way up. Space O(h) for the recursion.

Edge cases and pitfalls

Empty tree or single node. The property holds trivially and the conversion changes nothing.
One child. The node must equal that child. [3, 1, 2, null, 1] holds; [3, 1, 2, null, 0] does not, because 1 != 0.
Leaves are exempt. Do not compare a leaf with 0, or every non-zero leaf would fail.
Never decrease. The Java tests snapshot every value before converting and assert that none went down. A solution that sets a node to its children’s sum without first lifting the children would break this.
Growth and overflow. Values only grow; a node’s final value is the sum of the leaf values below it. With large inputs the root can exceed int, so switch to long if values can be big.
Different answers are fine. The two approaches produce different trees. Tests should check the property and the “no decrease” rule rather than one exact output.

Maximum Depth in BT uses the same post-order pattern: compute children first, then the parent.
Check for balanced binary tree is another bottom-up property check.
Diameter of Binary Tree combines values from both children at every node.
Maximum path sum does the same with path sums.