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 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.
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.
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.
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.
We first recursively traverse the left and right subtrees, then visit the root node.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space used for recursive calls.
The order of preorder traversal is: root, left, right. If we change the order of the left and right children, the order becomes: root, right, left. Finally, reversing the result gives us the postorder traversal result.
Therefore, the idea of using a stack to implement non-recursive traversal is as follows:
stk, and first push the root node into the stack.The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.
Python
Java
C++
Go
TypeScript
Morris traversal does not require a stack, and its space complexity is O(1). The core idea is:
Traverse the binary tree nodes,
root is empty, add the current node value to the result list ans, and update the current node to root.left.root is not empty, find the leftmost node next of the right subtree (which is the successor of the root node in inorder traversal):next is empty, add the current node value to the result list ans, then point the left subtree of the successor node to the current node root, and update the current node to root.right.next is not empty, point the left subtree of the successor node to null (i.e., disconnect next and root), and update the current node to root.left.The idea of Morris postorder traversal is consistent with Morris preorder traversal, just change the "root-left-right" of preorder to "root-right-left", and finally reverse the result to become "left-right-root".
The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| 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. |
| Recursion | — |
| Stack Implementation for Postorder Traversal | — |
| Morris Implementation for Postorder Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Postorder Traversal | O(n) | O(h) | Best for clarity and interviews when recursion is acceptable |
| Iterative Traversal using Two Stacks | O(n) | O(n) | When avoiding recursion or demonstrating stack-based traversal logic |
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python • NeetCodeIO • 56,847 views views
Watch 9 more video solutions →Practice Binary Tree Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCode