Pattern #43

Postorder Traversal

Important interview questions, thinking patterns, Children-First (L-R-Root) processing, Global vs Return Value distinction, Tree DP, and Go code templates.

Must Solve

16 core questions — solve these first.

1.Binary Tree Postorder Traversal
Left -> Right -> Root: process both children subtrees before processing current nodeeasy
2.Maximum Depth of Binary Tree
1 + max(leftHeight, rightHeight) after children return heightseasy
3.Diameter of Binary Tree
Global max(leftHeight + rightHeight), return 1 + max(leftHeight, rightHeight)easy
4.Balanced Binary Tree
Postorder height check: return -1 if |left - right| > 1 to stop earlyeasy
5.Binary Tree Maximum Path Sum
Global max(node.Val + max(0,left) + max(0,right)), return node.Val + max(0, max(left, right))hard
6.House Robber III
Postorder Tree DP returning [robCurrent, skipCurrent] tuple for each nodemedium
7.Delete Leaves With a Given Value
Postorder leaf deletion: process children first, check if node is now a target leafmedium
8.Find Leaves of Binary Tree
Postorder height grouping: leaves at height 0, parents at height 1medium
9.Longest Univalue Path
Postorder DFS matching child values to current node valuemedium
10.Maximum Difference Between Node and Descendant Variants
Postorder returning (minSubtree, maxSubtree) to parentmedium
11.Binary Tree Cameras
Postorder state DP: 0 (uncovered), 1 (has camera), 2 (covered)hard
12.Lowest Common Ancestor of a Binary Tree
Postorder: return node if root == p or q; check if left != nil && right != nilmedium
13.Subtree Sum Problems
Postorder: return leftSum + rightSum + node.Val to parentmedium
14.Count Nodes / Subtree Size
Postorder: return 1 + leftCount + rightCount to parenteasy
15.Sum of Subtree
Postorder: accumulate node.Val + leftSum + rightSumeasy
16.Tree DP Problems
Postorder state aggregation: combine child states into parent statemedium

Also Important

8 more questions worth practicing.

17.Minimum Depth of Binary Tree
Postorder DFS return min(left, right) handling single child non-null caseseasy
18.Distribute Coins in Binary Tree
Postorder: leftBalance + rightBalance + node.Val - 1; add abs(balance) to movesmedium
19.Smallest Subtree with All Deepest Nodes
Postorder DFS returning (depth, lcaNode) tuplemedium
20.Lowest Common Ancestor of Deepest Leaves
Postorder DFS comparing left and right subtree depthsmedium
21.Maximum Product of Split Binary Tree
Postorder to get totalSum first, then postorder to test (totalSum - sum) * summedium
22.Delete Nodes and Return Forest
Postorder leaf-to-root deletion disconnecting deleted child pointersmedium
23.Tree Pruning
Postorder bottom-up pruning of subtrees matching target criteriamedium
24.N-ary Tree Postorder Traversal
Iterate all children first, then append node.Valeasy

How to Think

Parent needs child answers first?Postorder Traversal (Left -> Right -> Root)
Need height / subtree size / sum?leftResult + rightResult + node.Val
Need diameter / maximum path?Children return info + Parent updates global answer
Need delete / prune based on children?Process children first, then decide parent

Go Postorder Code Templates

Recursive Postorder & Tree Height in Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 1. Standard Postorder: Left -> Right -> Root
func postorderRecursive(root *TreeNode) []int {
    result := []int{}
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        dfs(node.Right)
        result = append(result, node.Val) // Process Root Last!
    }
    dfs(root)
    return result
}

// 2. Postorder Tree Height Calculation
func treeHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := treeHeight(root.Left)
    rightHeight := treeHeight(root.Right)

    return 1 + max(leftHeight, rightHeight)
}

👉 Total Time: O(N) | Space: O(H) stack

Global Candidate vs Return Value Distinction

In Postorder algorithms like Diameter or Max Path Sum, there is a key difference between what gets returned upward to the parent versus what updates the global answer:

// Binary Tree Maximum Path Sum
func maxPathSum(root *TreeNode) int {
    maxSum := -1 << 31

    var postorder func(node *TreeNode) int
    postorder = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        // 1. Get child branch gains (Drop negative gains!)
        leftGain := max(0, postorder(node.Left))
        rightGain := max(0, postorder(node.Right))

        // 2. Update Global Candidate Answer (Uses BOTH branches!)
        candidate := node.Val + leftGain + rightGain
        if candidate > maxSum {
            maxSum = candidate
        }

        // 3. Return Upward to Parent (MUST choose ONLY ONE branch!)
        return node.Val + max(leftGain, rightGain)
    }

    postorder(root)
    return maxSum
}

👉 Return value uses 1 branch; Global candidate evaluates both branches!

Bottom-Up Tree Pruning & Tree DP

1. Bottom-Up Deletion: Problems like Delete Leaves with Target Value require deleting children first. When a child gets removed, the parent may become a new leaf node and get deleted in turn!

2. Tree DP (House Robber III): Each node returns a state tuple [robCurrent, skipCurrent] back up to its parent based on its subtrees.

Visual Memory Rule

Postorder       → LEFT -> RIGHT -> ROOT (Children finish first, parent last)
Return Upward   → Return ONE branch height / gain to parent
Global Answer   → Update with BOTH branches
Tree DP         → Children return state tuple [rob, skip] to parent
Negative Branch → max(0, childGain) (Ignore harmful paths!)

💡 Golden Rule: "Let both children finish their work first, then use their answers to decide the parent."

Common Interview Mistakes

1. Processing Parent Too Early

Postorder parent MUST wait until both left and right children subtrees finish processing!

2. Mixing Return Value with Global Answer

In Diameter / Max Path Sum, do NOT return both branches upward! Return node.Val + max(left, right) while updating global max with node.Val + left + right.

3. Recalculating Child Info Repeatedly

Do not call a separate height/sum function inside a DFS loop causing O(N²)! Return all required subtree info in a single DFS traversal.

4. Using Preorder for Bottom-Up Decisions

If parent decision depends on modified child states (e.g. deleting leaves or camera placement), Preorder will fail! You MUST use Postorder.

Interview Rules

1. Parent needs child answers first? → Postorder Traversal
2. Traversal sequence? → LEFT -> RIGHT -> ROOT
3. Height / Subtree Sum / Size? → leftResult + rightResult + node.Val
4. Diameter / Max Path Sum? → Children return single-branch gain; Parent updates global answer with both branches
5. Negative child contribution? → Ignore it using max(0, childGain)
6. Tree DP (House Robber III / Cameras)? → Postorder returning state tuple to parent
7. Bottom-Up Pruning (Delete Leaves)? → Process children first, then evaluate parent
8. Overall Complexity → Time: O(N) | Stack Space: O(H) (O(log N) balanced, O(N) skewed)

Small Rules

Rule 1: Postorder evaluates children first, parent last.
Rule 2: Subtree information returns UPWARD from children to parent.
Rule 3: Global candidate answer can use both branches, but return value upward uses only one branch.
Rule 4: Tree DP algorithms rely almost exclusively on Postorder state returns.
Rule 5: Bottom-up leaf deletion requires child subtrees to complete before evaluating parent node.

Production Thinking

Folder Size Calculation → Calculating size of all files & subfolders before computing total parent folder size

Dependency Hierarchy Cleanup → Safely destroying child sub-resources before deleting parent resources

UI Component Unmounting → Executing child lifecycle cleanup before unmounting parent container

Expression Evaluation (Postfix) → Evaluating operand child nodes first before performing operator calculation (2 + 3 * 4)

Remember This

Postorder       → LEFT -> RIGHT -> ROOT
Children        → First
Parent          → Last
Height          → Child heights then parent
Diameter        → Heights + global answer
Max Path        → Return one side, global uses both
Tree DP         → Postorder
Delete bottom-up→ Postorder
Subtree info    → Return UPWARD
Time            → O(N)

💡 Golden Rule: "Let both children finish their work first, then use their answers to decide the parent."