Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
[0, 100].-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
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.
The simplest way to perform a postorder traversal of a binary tree is recursively. In postorder traversal, you need to traverse the left subtree, then traverse the right subtree, finally visit the root node. This means visiting the left child, then the right child, and then the node itself for each node in the tree.
This C solution uses a helper function, postorderHelper, to perform the traversal recursively. It first processes the left child, then the right child, and finally the root node, appending each value to the result array. This order ensures a postorder traversal, which visits each node in the left-right-root order.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the binary tree, because each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursive call stack usage.
To perform postorder traversal iteratively, two stacks can be used. The first stack is used to perform a modified preorder traversal (root-right-left), while the second stack reverses this order to provide the postorder traversal (left-right-root). This approach allows the sequence of visiting nodes in postorder traversal without recursion.
This C implementation uses two stacks: the first stack (stack1) performs a modified preorder traversal (root-right-left); the second stack (stack2) is used to reverse the node visit order to achieve postorder (left-right-root) traversal. Values are ultimately extracted from the second stack.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) due to the usage of two stacks, each containing n nodes in the worst case for balanced or full trees.
| Approach | Complexity |
|---|---|
| Recursive Postorder Traversal | Time Complexity: O(n), where n is the number of nodes in the binary tree, because each node is visited once. |
| Iterative Postorder Traversal using Two Stacks | Time Complexity: O(n) where n is the number of nodes. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Postorder Traversal | O(n) | O(h) | Best for clarity and typical interview explanations; directly mirrors DFS traversal logic |
| Iterative Postorder Traversal (Two Stacks) | O(n) | O(n) | Useful when recursion is restricted or when demonstrating stack-based traversal techniques |
Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python • NeetCode • 307,238 views views
Watch 9 more video solutions →Practice Binary Tree Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor