Skip to content

Subtree Aggregation

When the Return Value IS the Answer

In the last lesson you learned pair-return: return one thing, track another. That pattern is powerful, but not every postorder problem needs it.

Many problems are simpler. You compute a value bottom-up, and what you return to the parent IS the answer — there's no second quantity to track on the side. The return value serves double duty: it's the answer at this node AND the ingredient the parent needs.

These are pure aggregation problems. They're the cleanest application of the postorder template.

Subtree sums bubbling upward: each node stores the sum of its entire subtree

Problem 1: Children Sum Property

Problem: Check whether every node in a binary tree satisfies the children sum property: each node's value equals the sum of its children's values. Leaf nodes trivially satisfy this (they have no children).

        10
       /  \
      8    2
     / \    \
    3   5    2

Node 8: children are 3 and 5. \(3 + 5 = 8\). Satisfied. Node 2: children are nullptr and 2. \(0 + 2 = 2\). Satisfied. Node 10: children are 8 and 2. \(8 + 2 = 10\). Satisfied.

All nodes pass. The tree satisfies the property.

The Approach

At each node, you need to know the VALUES of the left and right children (not the sums of entire subtrees — just the immediate children). This is actually simpler than typical postorder because you don't need recursive return values at all. You just check each node against its direct children.

But there's a clean postorder way to frame it: recurse to verify the children first, then check the current node. If any node fails, the whole tree fails.

bool checkChildrenSum(TreeNode* root) {
    if (!root) return true;
    if (!root->left && !root->right) return true;

    if (!checkChildrenSum(root->left)) return false;
    if (!checkChildrenSum(root->right)) return false;

    int leftVal = root->left ? root->left->val : 0;
    int rightVal = root->right ? root->right->val : 0;

    return root->val == leftVal + rightVal;
}

Trace

        10
       /  \
      8    2
     / \    \
    3   5    2
Call Node Left child val Right child val Sum Match? Returns
check(3) 3 — (leaf) — (leaf) — yes true
check(5) 5 — (leaf) — (leaf) — yes true
check(8) 8 3 5 8 yes true
check(2 right) 2 — (leaf) — (leaf) — yes true
check(2) 2 0 (no left) 2 2 yes true
check(10) 10 8 2 10 yes true

Every node passes. Tree satisfies the children sum property.

Problem 2: Binary Tree Tilt (LC 563)

Problem: The tilt of a node is \(|\text{sum of left subtree} - \text{sum of right subtree}|\). The tilt of the whole tree is the sum of every node's tilt. Return the total tilt.

        4
       / \
      2   9
     / \   \
    3   5   7

This one is interesting. You need the subtree SUM at each node (not just the height or the direct children). And you need to accumulate tilt across all nodes.

At first this looks like pair-return: you return the subtree sum, and you track the total tilt. And technically, yes, you do accumulate a running total. But it's a much simpler version — the accumulated value is just a counter that grows, not a max-over-all-nodes optimization. The core logic is pure aggregation: compute subtree sums bottom-up.

int totalTilt;

int subtreeSum(TreeNode* root) {
    if (!root) return 0;
    int leftSum = subtreeSum(root->left);
    int rightSum = subtreeSum(root->right);
    totalTilt += abs(leftSum - rightSum);
    return root->val + leftSum + rightSum;
}

int findTilt(TreeNode* root) {
    totalTilt = 0;
    subtreeSum(root);
    return totalTilt;
}

Trace

        4
       / \
      2   9
     / \   \
    3   5   7
Call Node leftSum rightSum Tilt at node totalTilt Returns (subtree sum)
subtreeSum(3) 3 0 0 $ 0 - 0 = 0$
subtreeSum(5) 5 0 0 $ 0 - 0 = 0$
subtreeSum(2) 2 3 5 $ 3 - 5 = 2$
subtreeSum(7) 7 0 0 $ 0 - 0 = 0$
subtreeSum(9) 9 0 7 $ 0 - 7 = 7$
subtreeSum(4) 4 10 16 $ 10 - 16 = 6$

Total tilt = \(0 + 0 + 2 + 0 + 7 + 6 = 15\).

Manual verification: left subtree sum of node 2 is 3, right is 5, tilt is 2. Left subtree sum of node 9 is 0, right is 7, tilt is 7. Left subtree sum of node 4 is 10, right is 16, tilt is 6. All other nodes are leaves with tilt 0. Total = \(2 + 7 + 6 = 15\). Correct.

Complexity: \(O(n)\) time, \(O(h)\) space.

Problem 3: Subtree Sums

Problem: For every node in the tree, compute the sum of all values in its subtree (including itself). Store the results.

This is the purest possible postorder aggregation — no tracking, no side effects, just bottom-up computation.

        1
       / \
      2   3
     / \
    4   5

int computeSubtreeSum(TreeNode* root, unordered_map<TreeNode*, int>& subtreeSums) {
    if (!root) return 0;
    int leftSum = computeSubtreeSum(root->left, subtreeSums);
    int rightSum = computeSubtreeSum(root->right, subtreeSums);
    int totalSum = root->val + leftSum + rightSum;
    subtreeSums[root] = totalSum;
    return totalSum;
}

Trace

Call Node leftSum rightSum Subtree sum Stored
compute(4) 4 0 0 4 sums[4] = 4
compute(5) 5 0 0 5 sums[5] = 5
compute(2) 2 4 5 11 sums[2] = 11
compute(3) 3 0 0 3 sums[3] = 3
compute(1) 1 11 3 15 sums[1] = 15

Each node stores the sum of its entire subtree. The root stores 15 (the sum of all values). Each leaf stores just its own value. This is the building block for many advanced tree algorithms.

Pure Aggregation vs. Pair-Return

Now you've seen both patterns. Here's how to tell them apart instantly:

Pure Aggregation Pair-Return
Return value IS the answer (or feeds directly into a simple accumulator) Is an INGREDIENT for the parent, not the answer itself
Answer The return value, or a simple sum of return values A combination of BOTH children that the parent can't use
Examples Subtree sum, tilt, children sum check Diameter, max path sum, longest univalue path
Global variable Optional (simple counter) Required (tracks the max/answer across all nodes)

Ask yourself: does the parent need the same thing I computed as my answer? If yes, it's pure aggregation. If the parent needs something different — a single branch instead of a two-branch combination — it's pair-return.

Children sum: the parent just checks its own children's values. Pure check. Tilt: the parent needs the subtree sum, and that's what you return. The tilt accumulation is a simple counter. Pure aggregation. Diameter: the parent needs your height, but the answer at your node is leftHeight + rightHeight. Different things. Pair-return.

Try It

The starter code has findTilt with a TODO. Implement it.

Input: (the tree built in main)
Output: 15

Predict before running: What is the tilt of a single-node tree? What about a tree where every node has the same value?

Challenge: Modify the subtree sum code to find the node with the maximum subtree sum. What do you track? What do you return? Is this pure aggregation or pair-return?

Challenge 2: Given a binary tree, count the number of "univalue subtrees" — subtrees where every node has the same value. Think about what your postorder function should return. Do you need to return the value? A boolean? Both?

Edge Cases to Watch For

  • Children sum with only one child: If a node has only a left child, the right child value is 0. The property becomes root->val == leftChild->val + 0. You must guard for the missing child with a ternary or null check — do not skip it.
  • Negative values in subtree sums: Subtree sums can be negative. The tilt uses absolute value, so \(|(-5) - 3| = 8\) not \(-8\). Make sure you use abs(), not a manual subtraction that could yield the wrong sign.

For the Curious — Edge Contribution Technique: When a problem asks "sum of X over all pairs of nodes," there's a powerful alternative to postorder: fix each edge and count its contribution. If removing edge \((u, v)\) splits the tree into components of size \(S\) and \(N - S\), the number of pairs crossing that edge is \(S \times (N - S)\). Sum this over all edges in one DFS pass — no rerooting needed.

Problems

Problem Link Difficulty
LC 563 — Binary Tree Tilt leetcode.com/problems/binary-tree-tilt Easy
LC 508 — Most Frequent Subtree Sum leetcode.com/problems/most-frequent-subtree-sum Medium
LC 250 — Count Univalue Subtrees leetcode.com/problems/count-univalue-subtrees Medium