Binary Tree Postorder Traversal - Video Solutions

Problem Overview: Given the root of a binary tree, return the postorder traversal of its nodes' values. Postorder means visiting nodes in the order left → right → root. The challenge is implementing this traversal correctly, especially when doing it iteratively without recursion.

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

The recursive solution directly follows the definition of postorder traversal. For each node, recursively traverse the left subtree, then the right subtree, and finally record the current node's value. The call stack implicitly acts as the traversal structure, which makes this the simplest implementation. The time complexity is O(n) because every node is visited once. Space complexity is O(h), where h is the tree height, due to recursion stack usage. This approach relies on Depth-First Search and is typically the first solution most engineers write.

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

The iterative approach avoids recursion by using two stacks. Push the root into the first stack. Repeatedly pop from this stack, push the node into the second stack, and push its left and right children into the first stack. This process effectively reverses a modified preorder traversal (root → right → left). When you finally pop elements from the second stack, the order becomes left → right → root, which is postorder. Each node moves through the stacks once, giving O(n) time complexity. Space complexity is O(n) because both stacks may store up to all nodes in the worst case. This method is useful when recursion depth is a concern and demonstrates strong understanding of stack-based traversal techniques in tree problems.

Recommended for interviews: Start with the recursive solution since it maps directly to the definition of postorder traversal and clearly demonstrates DFS reasoning. After that, discuss the iterative two-stack approach to show you understand how recursion can be simulated with explicit stack structures. Interviewers often expect the recursive solution first, while the iterative version signals deeper mastery of traversal mechanics.