Skip to content

Postorder Template

Platform Connection — Dependency Chaining: If you've taken our DP course, you know dependency chaining: value A can't be computed until values B and C are resolved. Postorder on a tree is exactly this. The root's answer literally cannot be computed until both children's answers are resolved first. The tree structure IS the dependency graph — and postorder is the algorithm that resolves it from the leaves (the base constraints) up to the root (the global output).

The Shape of Every Bottom-Up Solution

In Chapter 1 you saw countNodes and sumValues. Both followed the same shape: base case, recurse left, recurse right, combine. That shape has a name — postorder — and it's the workhorse of tree problem-solving.

This lesson formalizes it into a template you can apply mechanically. Once you see the template, you'll recognize it everywhere.

The template has exactly three steps:

  1. Base case. If the node is nullptr, return an identity value.
  2. Recurse. Get the answer from the left child. Get the answer from the right child.
  3. Combine. Merge the two child answers with the current node's information.

That's it. Every postorder problem is just choosing the right identity value and the right combine step.

The answer bubbles up from leaves to root. You never look down — you only look at what your children already computed.

Postorder template: base case returns identity, recurse on children, combine results at each node

Problem 1: Maximum Depth (LC 104)

Problem: Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root down to the farthest leaf.

        3
       / \
      9   20
         /  \
        15   7

The recursive question: if I knew the max depth of my left subtree and the max depth of my right subtree, could I compute mine?

Yes. My depth is \(1 + \max(\text{leftDepth}, \text{rightDepth})\).

Base case: nullptr has depth 0.

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + max(leftDepth, rightDepth);
}

Trace

Call Node leftDepth rightDepth Result
maxDepth(9) 9 0 0 1
maxDepth(15) 15 0 0 1
maxDepth(7) 7 0 0 1
maxDepth(20) 20 1 (from 15) 1 (from 7) 2
maxDepth(3) 3 1 (from 9) 2 (from 20) 3

The longest path is 3 → 20 → 15 (or 3 → 20 → 7), which has 3 nodes. Matches.

Problem 2: Balanced Binary Tree (LC 110)

Problem: Determine if a binary tree is height-balanced. A tree is balanced if, for every node, the heights of its left and right subtrees differ by at most 1.

        1
       / \
      2   3
     / \
    4   5

This is balanced. Every node satisfies \(|\text{leftHeight} - \text{rightHeight}| \leq 1\).

But this tree is not:

        1
       / \
      2   3
     / \
    4   5
   /
  6

At node 3, the left subtree has height 0, the right subtree has height 0 — fine. But at node 1, the left subtree has height 3, the right subtree has height 1 — difference is 2.

The Naive Approach

You could check each node individually: compute the height of its left subtree, compute the height of its right subtree, compare. But computing height is \(O(n)\), and you do it for each of the \(n\) nodes. That's \(O(n^2)\).

The Fix: Early Return with -1

Here's the trick: compute height bottom-up, but if any subtree is unbalanced, return \(-1\) instead of a real height. The \(-1\) propagates upward, poisoning every ancestor. When the root call gets \(-1\), the tree is unbalanced.

This needs two pieces of information at each node: the height (to pass to the parent) and whether it's balanced (to stop early). You might think you need to return a pair — and you could. But the \(-1\) sentinel handles both in a single integer.

This is a preview of the pair-return pattern you'll see in the next lesson. Here the sentinel value lets us dodge it, but soon you'll hit problems where you can't avoid returning two things.

int checkHeight(TreeNode* root) {
    if (!root) return 0;

    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) return -1;

    int rightHeight = checkHeight(root->right);
    if (rightHeight == -1) return -1;

    if (abs(leftHeight - rightHeight) > 1) return -1;

    return 1 + max(leftHeight, rightHeight);
}

bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

Trace (Balanced Tree)

        1
       / \
      2   3
     / \
    4   5

| Call | Node | leftHeight | rightHeight | |left - right| | Result | |------|------|------------|-------------|----------------|--------| | checkHeight(4) | 4 | 0 | 0 | 0 | 1 | | checkHeight(5) | 5 | 0 | 0 | 0 | 1 | | checkHeight(2) | 2 | 1 | 1 | 0 | 2 | | checkHeight(3) | 3 | 0 | 0 | 0 | 1 | | checkHeight(1) | 1 | 2 | 1 | 1 | 3 |

No \(-1\) anywhere. Tree is balanced.

Trace (Unbalanced Tree)

        1
       / \
      2   3
     / \
    4   5
   /
  6

| Call | Node | leftHeight | rightHeight | |left - right| | Result | |------|------|------------|-------------|----------------|--------| | checkHeight(6) | 6 | 0 | 0 | 0 | 1 | | checkHeight(4) | 4 | 1 (from 6) | 0 | 1 | 2 | | checkHeight(5) | 5 | 0 | 0 | 0 | 1 | | checkHeight(2) | 2 | 2 (from 4) | 1 (from 5) | 1 | 3 | | checkHeight(3) | 3 | 0 | 0 | 0 | 1 | | checkHeight(1) | 1 | 3 (from 2) | 1 (from 3) | 2 | -1 |

The difference at node 1 is 2, which exceeds 1. Returns \(-1\). Tree is unbalanced.

Complexity: \(O(n)\) time, \(O(h)\) space where \(h\) is the height (recursion stack).

Problem 3: Count Complete Tree Nodes (LC 222)

Problem: Given a complete binary tree, count the number of nodes. A complete binary tree has every level fully filled except possibly the last, which is filled left to right.

        1
       / \
      2   3
     / \  /
    4  5  6

The brute force is the countNodes from Chapter 1 — \(O(n)\). But a complete binary tree has extra structure. Can you do better?

The key observation: in a complete binary tree, at least one of the two subtrees is a perfect binary tree (all levels completely filled). A perfect binary tree of height \(h\) has exactly \(2^h - 1\) nodes — you don't need to recurse into it.

How do you check if a subtree is perfect? Compute the height going all the way left and all the way right. If they're equal, it's perfect.

int countNodes(TreeNode* root) {
    if (!root) return 0;

    int leftHeight = 0;
    int rightHeight = 0;
    TreeNode* leftRunner = root;
    TreeNode* rightRunner = root;

    while (leftRunner) {
        leftHeight++;
        leftRunner = leftRunner->left;
    }
    while (rightRunner) {
        rightHeight++;
        rightRunner = rightRunner->right;
    }

    if (leftHeight == rightHeight) {
        return (1 << leftHeight) - 1;
    }

    return 1 + countNodes(root->left) + countNodes(root->right);
}

Trace

        1
       / \
      2   3
     / \  /
    4  5  6
Call Node leftHeight rightHeight Perfect? Result
countNodes(4) 4 1 1 Yes \(2^1 - 1 = 1\)
countNodes(5) 5 1 1 Yes \(2^1 - 1 = 1\)
countNodes(2) 2 2 2 Yes \(2^2 - 1 = 3\)
countNodes(6) 6 1 1 Yes \(2^1 - 1 = 1\)
countNodes(3) 3 2 1 No 1 + countNodes(6) + countNodes(nullptr) = 1 + 1 + 0 = 2
countNodes(1) 1 3 2 No 1 + 3 + 2 = 6

Manual count: nodes 1, 2, 3, 4, 5, 6 = 6. Matches.

Notice how the left subtree (rooted at 2) was perfect — we computed its size in \(O(\log n)\) without entering it. The right subtree (rooted at 3) wasn't perfect, so we recursed. At each level, one subtree is skipped. Total time: \(O(\log^2 n)\).

Complexity: \(O(\log^2 n)\) time, \(O(\log n)\) space.

The Template, Formalized

Every problem in this lesson — and most problems in this chapter — follows this skeleton:

ResultType solve(TreeNode* root) {
    if (!root) return IDENTITY;
    ResultType leftResult = solve(root->left);
    ResultType rightResult = solve(root->right);
    return combine(root->val, leftResult, rightResult);
}

The only things that change between problems:

Component Max Depth Balanced Check Count Complete
IDENTITY 0 0 0
combine \(1 + \max(L, R)\) check diff, return height or \(-1\) perfect shortcut or \(1 + L + R\)

Postorder means: children first, parent second. By the time you process a node, you already have complete information from both subtrees. This is why postorder is the natural fit for bottom-up computation.

Try It

The starter code has a maxDepth function with a TODO. Fill it in.

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

Predict before running: What does maxDepth return on an empty tree (nullptr)? What about a single node with no children?

Challenge: Modify checkHeight to return the actual height when the tree is balanced, and \(-1\) when unbalanced. Then write a wrapper isBalanced that calls it. Test on both the balanced and unbalanced trees from the traces above.

Challenge 2: Can you solve Count Complete Tree Nodes in \(O(n)\) without using the perfect-tree shortcut? Of course — it's just countNodes from Chapter 1. Now think about why the \(O(\log^2 n)\) version matters. What if the tree has a million nodes?

Edge Cases to Watch For

  • Off-by-one in height definitions: Some problems define height as number of nodes on the longest path (LC 104), others as number of edges. nullptr returning 0 vs \(-1\) changes the answer by 1. Match the base case to the problem's definition.
  • Complete tree node count on a non-complete tree: The \(O(\log^2 n)\) optimization detects perfect subtrees via left-height vs right-height. If the tree is NOT complete (violating the precondition), this shortcut gives wrong answers. Only use it when the problem guarantees completeness.

Problems

Problem Link Difficulty
LC 104 — Maximum Depth of Binary Tree leetcode.com/problems/maximum-depth-of-binary-tree Easy
LC 110 — Balanced Binary Tree leetcode.com/problems/balanced-binary-tree Easy
LC 222 — Count Complete Tree Nodes leetcode.com/problems/count-complete-tree-nodes Medium