The O(n) Club: Binary Tree Postorder Traversal—Why the Cleanup Crew Wins

The O(n) Club: Binary Tree Postorder Traversal—Why the Cleanup Crew Wins

⚡ TL;DR

You want to visit the left child, then the right child, then the node itself. That’s postorder. Brute force? Recursion. Interviewers? Prefer iterative—because nothing says “I suffer for this job” quite like wrangling two stacks in Java.

Here’s the lazy-proof version:

// Java recursive postorder traversal
void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    System.out.print(node.val + " ");
}

🧠 How Devs Usually Mess This Up

Raise your hand if you’ve ever turned a postorder traversal into preorder or inorder by pure copy-paste magic (and left the root in the wrong spot). Most devs do this at least once: print the node too early, get the order backwards, or try to “just wing it” with a single stack in a fit of algorithmic optimism. Pro tip: your tree will look like an apocalyptic LinkedList if you do.

🔍 What’s Actually Going On

Think of postorder as the world’s most responsible babysitter: nobody leaves until all the kids are accounted for. In other words, you deal with both subtrees before the parent. Great for safely deleting trees—because deleting the parent before the kids is how you get memory leaks and side eyes from C developers. And if you’re parsing expressions? Postorder gives you Reverse Polish, aka calculator food.

🛠️ PseudoCode

• Recursion (The Easy Button):
  • If current node is null, return. if (node == null) return;
  • Traverse left: postorder(node.left)
  • Traverse right: postorder(node.right)
  • Process node: process(node)
• Iterative (Why Are You Like This):
  • Initialize two stacks: one for nodes, one for output.
  • Push root to stack1.
  • While stack1 isn’t empty:
    • Pop node from stack1, push to stack2.
    • Push left child to stack1 (if it exists).
    • Push right child to stack1 (if it exists).
  • Once done, pop everything from stack2 (which is now in postorder).