Binary Tree Postorder Traversal - Video Solutions

Problem Overview: Given the root of a binary tree, return the nodes in postorder traversal. Postorder means visiting the left subtree, then the right subtree, and finally the current node. The challenge is producing this order efficiently using either recursion or an explicit stack.

Approach 1: Recursive Postorder Traversal (O(n) time, O(h) space)

The recursive solution mirrors the definition of postorder traversal. Start a depth‑first search from the root. Recursively process the left child, then recursively process the right child, and finally append the current node's value to the result list. Each node is visited exactly once, so the total time complexity is O(n). The space complexity is O(h), where h is the height of the tree, due to the recursion call stack. This approach is concise and easy to reason about, which makes it a common baseline when working with tree traversal problems and depth-first search patterns.

Approach 2: Iterative Postorder Traversal using Two Stacks (O(n) time, O(n) space)

The iterative method avoids recursion by using explicit stack structures. Push the root into the first stack. Repeatedly pop a node, push it into a second stack, then push its left and right children into the first stack. This process effectively creates a modified preorder traversal (root → right → left). When you pop all nodes from the second stack, the order becomes left → right → root, which is exactly postorder. Every node moves through the stacks once, giving O(n) time complexity. Space complexity becomes O(n) because both stacks may store many nodes.

The key insight behind the two‑stack approach is reversing a traversal order. Preorder normally produces root → left → right. By pushing children in a specific order and reversing the result through another stack, you transform it into postorder. This technique appears frequently in iterative binary tree traversal implementations when recursion is not preferred.

Recommended for interviews: The recursive solution is usually the first answer interviewers expect because it directly follows the DFS definition of postorder traversal and is easy to implement correctly. After presenting it, showing the iterative two‑stack approach demonstrates deeper understanding of stack-based tree traversal and how recursion can be simulated with explicit data structures.