Binary Tree Postorder Traversal - Recursive, Iterative & Morris Solutions

Introduction

Postorder traversal follows the Left → Right → Root pattern:

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the current node (last!)

Why Process Children First?

Postorder is crucial when you need to:

• Process children before parent (bottom-up computation)
• Delete tree nodes safely (delete children before parent)
• Calculate subtree properties (height, size, sum)

When to Use Postorder

• Tree deletion (free children before parent)
• Expression tree evaluation (operands before operator)
• Calculate tree height/depth
• Serialize tree for reconstruction
• Dependency resolution (process dependencies first)

Visual Intuition

        1
       / \
      2   3
     / \
    4   5

Postorder: 4 → 5 → 2 → 3 → 1
           (Left→Right→Root)

Visit order:
  Step 1: Go left to 2, then left to 4
  Step 2: Visit 4 (no children)
  Step 3: Backtrack, go right to 5, Visit 5
  Step 4: Backtrack, Visit 2 (both children done)
  Step 5: Backtrack to 1, go right, Visit 3
  Step 6: Backtrack, Visit 1 (root last!)

The Key Insight

In postorder, a node is visited after all its descendants. This is why:

• Root 1 is visited last
• Each parent is visited after its children

Interactive Visualizer

Watch postorder traversal step by step. Notice how parent nodes wait until children are done!

Method:RecursiveIterativeMorris

Speed:0.5x1x2x4x

Postorder (Left→Right→Root) - Iterative

Step 1 / 0INIT

Ready to start

Stack

Empty

Result

[]

Current

Visited

In Stack

⟲ Reset← Prev▶ PlayNext →

Solution 1: Recursive Approach

The cleanest solution: recurse left, recurse right, then visit.

Code Template

JavaPythonJavaScript

Loading...

How It Works

1. Base case: If node is null, return
2. Recurse left: Process entire left subtree
3. Recurse right: Process entire right subtree
4. Visit root: Finally add current node’s value

The recursion naturally ensures children are processed before parents.

Solution 2: Iterative Approach

Postorder is the trickiest to implement iteratively. There are two common approaches:

Approach A: Reverse Preorder Trick

Insight: Postorder (L→R→Root) is the reverse of modified preorder (Root→R→L)

Modified Preorder: Root → Right → Left  = [1, 3, 2, 5, 4]
Reverse it:        Left → Right → Root  = [4, 5, 2, 3, 1] ✓ Postorder!

JavaPythonJavaScript

Loading...

Approach B: Classic with Previous Pointer

Track the previously visited node to know when right subtree is done:

JavaPythonJavaScript

Loading...

Comparison

Approach	Time	Space	Complexity
Reverse Preorder	O(n)	O(n)	Simple
Previous Pointer	O(n)	O(h)	Tricky

The previous pointer approach uses less space but requires careful handling.

Solution 3: Morris Traversal (O(1) Space)

Morris postorder is the most complex of all three traversals. It requires:

1. A dummy node as the parent of root
2. Reversing and collecting right-path segments

Code Template

JavaPythonJavaScript

Loading...

How It Works

Tree with dummy:
     dummy
      /
     1
    / \
   2   3

When thread from 3→dummy is found (returning):
1. Collect path from 1 to 3 in reverse: [3, 1]
   Wait, we need [1, 3] reversed = [3, 1]? No!
   
Actually: Collect 1→2→5→3 path, reverse to get [3, 5, 2, 1]... 

This is complex! The reverse operation collects nodes from
current.left to predecessor in reverse order.

Why So Complex?

Postorder visits roots last, but Morris traversal processes nodes while going “down” (via threads). We need to:

1. Collect a path of right-child pointers
2. Reverse it to get postorder
3. Reverse it back to restore tree

Recommendation: In interviews, use the reverse preorder trick unless explicitly asked for O(1) space.

LeetCode 145: Binary Tree Postorder Traversal (LC 145)

The classic postorder problem.

Example:

Input: root = [1,null,2,3]
    1
     \
      2
     /
    3

Output: [3, 2, 1]

Application: Safe Tree Deletion

Postorder is essential for deleting tree nodes:

// Delete all nodes in a tree safely
void deleteTree(TreeNode node) {
    if (node == null) return;
    
    deleteTree(node.left);   // Delete left subtree first
    deleteTree(node.right);  // Delete right subtree
    
    // Now safe to delete current node
    // (no dangling pointers to children)
    node.left = null;
    node.right = null;
    // node is now safe to garbage collect
}

Application: Calculate Tree Height

def treeHeight(root):
    if not root:
        return 0
    
    # Postorder: get children heights first
    left_height = treeHeight(root.left)
    right_height = treeHeight(root.right)
    
    # Then compute current node's height
    return 1 + max(left_height, right_height)

Complexity Analysis

Method	Time	Space	Notes
Recursive	O(n)	O(h)	Call stack depth = tree height
Iterative (Reverse)	O(n)	O(n)	Result stored in reverse
Iterative (Prev)	O(n)	O(h)	Stack size = tree height
Morris	O(n)	O(1)	Most complex implementation

Common Mistakes

1. Iterative: Wrong Push Order

// For reverse preorder trick:
// WRONG: Same as preorder (gives reversed postorder... wait, that's what we want!)
// Actually, we want Root→Right→Left, then reverse

// Push left FIRST (so right is processed first = Root→Right→Left)
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);

2. Previous Pointer: Forgetting to Reset Current

# WRONG: current still points to popped node
prev = stack.pop()
# Will try to go left from already-visited node!

# CORRECT: Set current to None
prev = stack.pop()
current = None  # Don't go left again

3. Confusing with Other Traversals

Remember the patterns:
- Preorder:  Root → Left → Right  (visit FIRST)
- Inorder:   Left → Root → Right  (visit MIDDLE)
- Postorder: Left → Right → Root  (visit LAST)

Edge Cases

1. Empty tree: Return []
2. Single node: Return [root.val]
3. Left-only tree: 1→2→3 gives [3, 2, 1]
4. Right-only tree: Same pattern
5. Complete binary tree: Standard case

Interview Tips

How to Explain Postorder

1. “Postorder visits nodes after all descendants are done”
2. “It’s Left → Right → Root order”
3. “Useful when you need bottom-up processing”
4. “The iterative version can use reverse preorder trick”

Which Iterative Approach?

Situation	Recommendation
Quick implementation	Reverse preorder
O(h) space required	Previous pointer
Asked for O(1) space	Morris (complex!)
Coding interview	Reverse preorder (safe choice)

Follow-up Questions

• “Can you do it without reversing?” → Previous pointer approach
• “O(1) space?” → Morris, but warn about complexity
• “When is postorder better than preorder?” → Bottom-up computations
• “Real-world use cases?” → Tree deletion, dependency graphs

Comparison of All Three Traversals

Tree:       1
           / \
          2   3
         / \
        4   5

Preorder:  [1, 2, 4, 5, 3]  Root first
Inorder:   [4, 2, 5, 1, 3]  Root in middle
Postorder: [4, 5, 2, 3, 1]  Root last

Property	Preorder	Inorder	Postorder
Root position	First	Middle	Last
Use case	Clone tree	BST sorted	Delete tree
Iterative ease	Easy	Medium	Hard
Morris ease	Medium	Medium	Hard

Summary

Aspect	Recursive	Iterative	Morris
Simplicity	⭐⭐⭐	⭐⭐	⭐
Space	O(h)	O(h) or O(n)	O(1)
Interview choice	Warmup	Primary	Advanced

Key Patterns to Remember:

1. Postorder = Left → Right → Root
2. Iterative trick: Reverse of Root → Right → Left
3. Visit parent AFTER all children
4. Perfect for bottom-up tree operations

Postorder is the trickiest traversal to implement iteratively, but understanding it deeply shows mastery of tree algorithms!