Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Approach 1: Recursive DFS
Algorithm
- Recursively traverse left subtree
- Recursively traverse right subtree
- Process current node (add to result)
Solution
Python:
def postorderTraversal(root):
"""
Recursive DFS approach
Time: O(n) - visit each node once
Space: O(h) - recursion stack depth
"""
result = []
def dfs(node):
if not node:
return
# Postorder: left -> right -> root
dfs(node.left)
dfs(node.right)
result.append(node.val)
dfs(root)
return result
Java:
class Solution {
/**
* Recursive DFS approach
* Time: O(n) - visit each node once
* Space: O(h) - recursion stack depth
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode node, List<Integer> result) {
if (node == null) return;
// Postorder: left -> right -> root
dfs(node.left, result);
dfs(node.right, result);
result.add(node.val);
}
}
Go:
// postorderTraversal - Recursive DFS approach
// Time: O(n) - visit each node once
// Space: O(h) - recursion stack depth
func postorderTraversal(root *TreeNode) []int {
var result []int
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
// Postorder: left -> right -> root
dfs(node.Left)
dfs(node.Right)
result = append(result, node.Val)
}
dfs(root)
return result
}
JavaScript:
/**
* Recursive DFS approach
* Time: O(n) - visit each node once
* Space: O(h) - recursion stack depth
*/
function postorderTraversal(root) {
const result = [];
function dfs(node) {
if (!node) return;
// Postorder: left -> right -> root
dfs(node.left);
dfs(node.right);
result.push(node.val);
}
dfs(root);
return result;
}
C#:
public class Solution {
/// <summary>
/// Recursive DFS approach
/// Time: O(n) - visit each node once
/// Space: O(h) - recursion stack depth
/// </summary>
public IList<int> PostorderTraversal(TreeNode root) {
var result = new List<int>();
Dfs(root, result);
return result;
}
private void Dfs(TreeNode node, List<int> result) {
if (node == null) return;
// Postorder: left -> right -> root
Dfs(node.left, result);
Dfs(node.right, result);
result.Add(node.val);
}
}
Approach 2: Iterative with Stack
Algorithm
- Use stack to simulate recursion
- Push root to stack
- While stack is not empty:
- Pop node and add to result
- Push left child first, then right child
- Reverse result to get postorder
Solution
Python:
def postorderTraversal(root):
"""
Iterative approach using stack
Time: O(n) - visit each node once
Space: O(h) - stack storage
"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push left first, then right
# This ensures right is processed before left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
# Reverse to get postorder (left -> right -> root)
return result[::-1]
Java:
class Solution {
/**
* Iterative approach using stack
* Time: O(n) - visit each node once
* Space: O(h) - stack storage
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
// Push left first, then right
// This ensures right is processed before left
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
// Reverse to get postorder (left -> right -> root)
Collections.reverse(result);
return result;
}
}
Go:
// postorderTraversal - Iterative approach using stack
// Time: O(n) - visit each node once
// Space: O(h) - stack storage
func postorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
var result []int
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, node.Val)
// Push left first, then right
// This ensures right is processed before left
if node.Left != nil {
stack = append(stack, node.Left)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
}
// Reverse to get postorder (left -> right -> root)
for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
result[i], result[j] = result[j], result[i]
}
return result
}
JavaScript:
/**
* Iterative approach using stack
* Time: O(n) - visit each node once
* Space: O(h) - stack storage
*/
function postorderTraversal(root) {
if (!root) return [];
const result = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// Push left first, then right
// This ensures right is processed before left
if (node.left) {
stack.push(node.left);
}
if (node.right) {
stack.push(node.right);
}
}
// Reverse to get postorder (left -> right -> root)
return result.reverse();
}
C#:
public class Solution {
/// <summary>
/// Iterative approach using stack
/// Time: O(n) - visit each node once
/// Space: O(h) - stack storage
/// </summary>
public IList<int> PostorderTraversal(TreeNode root) {
var result = new List<int>();
if (root == null) return result;
var stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
var node = stack.Pop();
result.Add(node.val);
// Push left first, then right
// This ensures right is processed before left
if (node.left != null) {
stack.Push(node.left);
}
if (node.right != null) {
stack.Push(node.right);
}
}
// Reverse to get postorder (left -> right -> root)
result.Reverse();
return result;
}
}
Key Insights
- Postorder Order: Left subtree → Right subtree → Root
- Use Cases: Postorder is useful for deleting trees, calculating directory sizes, and expression evaluation
- Stack Simulation: Iterative approach simulates recursion using explicit stack
- Reversal Trick: Push right child first, then left child, then reverse the result
Edge Cases
- Empty Tree: Return empty list
- Single Node: Return list with single element
- Linear Tree: Tree that looks like a linked list
- Complete Binary Tree: Tree with all levels filled
Follow-up Questions
- Iterative without reversing: Can you implement postorder traversal iteratively without reversing the result?
- N-ary tree: Extend to N-ary trees
- Threaded binary tree: Implement using threaded binary tree structure
- Parallel traversal: How would you parallelize postorder traversal?
Common Mistakes
- Wrong order: Confusing with preorder or inorder
- Stack implementation: Not handling the reversal correctly in iterative approach
- Null checks: Forgetting to check for null nodes
- Space complexity: Not considering recursion stack space