09.Postorder2.md

🌳 Postorder Traversal in Binary Tree (Recursive & Iterative) #145

📌 Problem Statement

Given the root of a Binary Tree, return the postorder traversal of its nodes.

👉 Postorder Traversal Order:

Left → Right → Root

🧠 Why Postorder Traversal is special

Postorder traversal is the most “bottom-up” traversal.

It is heavily used in:

• Deleting a tree
• Tree DP problems
• Height / Diameter / Balance checks
• Expression tree evaluation

If preorder says “me first” and inorder says “me in between” then postorder says:

“Kids first… I’ll go last.” 😌

👀 Example

Binary Tree:

        1
       / \
      2   3
     / \
    4   5

Postorder Output

4 5 2 3 1

1️⃣ Recursive Postorder Traversal 🌱 (Simplest)

✅ Recursive Code

class Solution {
public:
    void postorderTraversal(TreeNode* root, vector<int>& result) {

        if (!root) return;

        postorderTraversal(root->left, result);
        postorderTraversal(root->right, result);
        result.push_back(root->val);
    }
};

🧠 Algorithm (Recursive)

If root is NULL:
    return

Postorder(left)
Postorder(right)
Visit root

⏱ Complexity

• Time: O(N)
• Space: O(H) recursion stack (H = height of tree)

⚠️ Risk of stack overflow in degenerate trees

🧩 When to use recursion

• When tree depth is small
• When clarity matters more than stack limits
• When interviewer doesn’t restrict recursion

2️⃣ Iterative Postorder Traversal (Using Two Stacks) 🧱🔥

This is the most common iterative postorder solution.

✅ Cleaned CPP Code

vector<int> postorderTraversal(Node* root) {
    vector<int> postorder;
    if (!root) return postorder;

    stack<Node*> st1, st2;
    st1.push(root);

    while (!st1.empty()) {
        Node* node = st1.top();
        st1.pop();
        st2.push(node);

        if (node->left) st1.push(node->left);
        if (node->right) st1.push(node->right);
    }

    while (!st2.empty()) {
        postorder.push_back(st2.top()->val);
        st2.pop();
    }

    return postorder;
}

🧠 Core Intuition (VERY IMPORTANT)

Postorder =

Left → Right → Root

But iterative traversal naturally gives:

Root → Left → Right

So the trick is:

1. Generate Root → Right → Left
2. Reverse it → Left → Right → Root

That’s exactly what two stacks do 🎯

🧠 Algorithm (Two Stacks)

1. Push root into st1
2. Pop from st1, push into st2
3. Push left & right children into st1
4. Once done, pop from st2 → postorder

⏱ Complexity

• Time: O(N)
• Space: O(N) (two stacks)

✔ No recursion ✔ No stack overflow risk

🧪 Test Cases

Tree Type	Output
Empty tree	[]
Single node	[1]
Left skewed	bottom → root
Right skewed	bottom → root
Balanced tree	children before parent

🧠 Comparison: Recursive vs Two-Stack Iterative

Aspect	Recursive	Iterative (2 stacks)
Simplicity	⭐⭐⭐⭐⭐	⭐⭐⭐
Space	O(H)	O(N)
Stack overflow risk	Yes	No
Interview usage	Very common	Very common

⚠️ Common Interview Mistakes

❌ Forgetting root null check

❌ Pushing children in wrong order

❌ Mixing preorder logic

❌ Forgetting why reversal is needed

🚀 Variations & Related Problems

• Postorder using single stack (harder)
• Morris Postorder Traversal (O(1) space)
• Tree deletion
• Expression tree evaluation
• Diameter / height / balanced tree checks

❓ FAQs

Q1: Why is postorder hardest to do iteratively?

Because root comes last, not first or middle.

Q2: Which iterative postorder should I remember?

👉 Two-stack approach It’s the safest and most explainable.

Q3: When should I avoid recursion?

• Very deep trees
• Memory-restricted environments

Q4: Is Morris postorder required in interviews?

Almost never ❌ Good to know, not required.

Q5: Can postorder traversal sort a BST?

No ❌ Only inorder traversal sorts BST values.

🧠 Quick Revision Cheat Sheet 📝

Postorder = Left → Right → Root
Recursive = easiest
Iterative = reverse (Root → Right → Left)
Two stacks = safest