Introduction

LeetCode 145 – Binary Tree Postorder Traversal is one of the most important tree traversal problems for beginners learning Data Structures and Algorithms.

This problem teaches:

1. Binary Tree Traversal
2. Depth First Search (DFS)
3. Recursion
4. Stack-based traversal
5. Tree traversal patterns

Postorder traversal is extremely useful in advanced tree problems such as:

1. Tree deletion
2. Expression tree evaluation
3. Bottom-up computations
4. Dynamic programming on trees

Problem Link

🔗 https://leetcode.com/problems/binary-tree-postorder-traversal/

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes' values.

What is Postorder Traversal?

In postorder traversal, nodes are visited in this order:

Unlike preorder or inorder traversal, the root node is processed at the end.

Example

Input

Tree Structure:

Postorder Traversal

Traversal order:

Output:

Recursive Approach (Most Common)

Intuition

In postorder traversal:

1. Traverse left subtree
2. Traverse right subtree
3. Visit current node

This naturally fits recursion because trees themselves are recursive structures.

Recursive DFS Visualization

Traversal pattern:

Recursive function:

Java Recursive Solution

Dry Run – Recursive Approach

Tree:

Step 1

Start at:

Move left:

Return back.

Step 2

Move right to:

Move left to:

Left and right of 3 are null.

Add:

Step 3

Return to:

Add:

Step 4

Return to:

Add:

Final Answer

Time Complexity – Recursive

Time Complexity

Every node is visited once.

Space Complexity

Where:

1. H = height of the tree
2. Recursive call stack uses extra space

Worst case:

for skewed trees.

Iterative Approach (Interview Follow-Up)

The follow-up asks:

Can you solve it iteratively?

Yes.

We use stacks to simulate recursion.

Iterative Postorder Intuition

Postorder traversal order is:

One common trick is:

1. Traverse in modified preorder:

1. Reverse the result.

After reversing, we get:

which is postorder traversal.

Stack-Based Iterative Logic

Algorithm

1. Push root into stack.
2. Pop node.
3. Add node value to answer.
4. Push left child.
5. Push right child.
6. Reverse final answer.

Java Iterative Solution

Dry Run – Iterative Approach

Tree:

Step 1

Push:

Step 2

Pop:

Add at front:

Push right child:

Step 3

Pop:

Add at front:

Push left child:

Step 4

Pop:

Add at front:

Final Answer

Comparison of Approaches

Interview Explanation

In interviews, explain:

Postorder traversal processes nodes in Left → Right → Root order. Recursion naturally handles this traversal. Iteratively, we simulate recursion using a stack and reverse traversal order.

This demonstrates strong tree traversal understanding.

Common Mistakes

1. Wrong Traversal Order

Incorrect:

That is preorder traversal.

Correct postorder:

2. Forgetting Null Base Case

Always check:

3. Incorrect Stack Push Order

For iterative solution:

1. Push left first
2. Push right second

because we reverse the result later.

FAQs

Q1. Why is postorder traversal useful?

It is used in:

1. Tree deletion
2. Expression tree evaluation
3. Bottom-up dynamic programming
4. Calculating subtree information

Q2. Which approach is preferred in interviews?

Recursive is simpler.

Iterative is often asked as a follow-up.

Q3. Can postorder traversal be done without stack or recursion?

Yes.

Using Morris Traversal.

Q4. What is the difference between preorder, inorder, and postorder?

Bonus: Morris Postorder Traversal

Morris traversal performs tree traversal using:

extra space.

This is considered an advanced interview topic.

Conclusion

LeetCode 145 is an excellent beginner-friendly tree traversal problem.

It teaches:

1. DFS traversal
2. Recursion
3. Stack simulation
4. Binary tree fundamentals

The key postorder pattern is:

Mastering this traversal helps in solving many advanced tree problems such as:

1. Tree DP
2. Tree deletion
3. Expression evaluation
4. Subtree calculations
5. Advanced DFS problems