Postorder traversal is one of the three fundamental strategies for performing depth-first search (DFS) on binary trees. It’s unique in its traversal order: left subtree → right subtree → root, ensuring that all child nodes are visited before their parent node. This traversal order makes postorder traversal particularly valuable in certain real-world applications.
How Postorder Traversal Works
In postorder traversal, each node is visited only after its left and right subtrees have been fully explored. The recursive nature of this traversal closely mirrors how hierarchical structures are processed in many computational problems.
Traversal Order:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root node.
Exploring Approaches to Postorder Traversal: Recursive Solution
When solving binary tree problems, the recursive approach to postorder traversal stands out for its simplicity and direct alignment with the traversal’s definition: left subtree → right subtree → root. This method leverages recursion to naturally explore each part of the tree in the correct order, making it an excellent starting point for learning and understanding postorder traversal.
How the Recursive Approach Works
The recursive approach follows the core principle of divide and conquer:
1. Recursively Traverse the Left Subtree:
• Start with the left child of the current node and continue exploring its descendants until you reach a leaf node.
2. Recursively Traverse the Right Subtree:
• After finishing the left subtree, move to the right child of the current node and repeat the process.
3. Process the Root Node:
• Once both subtrees are fully traversed, visit the root node and perform the required operation (e.g., adding its value to a result list).
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return; // Base case: Stop at null nodes
postorderHelper(node.left, result); // Traverse left subtree
postorderHelper(node.right, result); // Traverse right subtree
result.add(node.val); // Process root node
}
}Limitations of the Recursive Approach
1. Stack Overflow:
• For very deep or skewed trees, recursion may exceed the maximum call stack size, leading to a stack overflow error.
2. Space Usage:
• The recursion stack requires O(h) space, where h is the height of the tree.
Mastering the Iterative Approach to Postorder Traversal
While recursion is the most intuitive way to perform postorder traversal, it can lead to stack overflow for deep trees and lacks the control offered by an iterative approach. Using a stack, we can simulate the behavior of recursion and efficiently perform postorder traversal—left subtree → right subtree → root—even for large or deeply nested trees.
The iterative approach is particularly useful in environments where recursion depth is limited or explicit control over traversal is required. However, achieving postorder traversal iteratively can be challenging because the root must be processed after both subtrees. Let’s break down how this is accomplished.
How the Iterative Approach Works
To mimic the recursive process, the iterative approach uses a stack to track nodes during traversal. The root node is visited only after its left and right subtrees have been processed. This requires careful ordering of nodes in the stack. The key steps include:
1. Use a Stack for Traversal:
• A stack is used to simulate the recursive call stack, storing nodes as you traverse the tree.
2. Handle Root After Subtrees:
• To ensure the root is processed last, you can:
• Use a visited flag to track nodes that have already been processed.
• Use a second stack to reverse the traversal order.
3. Reverse the Order:
• Postorder traversal is essentially the reverse of preorder traversal when the order is “root → right → left.” By reversing the preorder sequence, you can achieve the desired postorder sequence.
Two Approaches To Iterative Post Order Traversal:
1. Two-Stack Method
This method uses one stack to traverse the tree in “root → right → left” order and another stack to store the nodes in reverse, achieving “left → right → root.”
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) stack1.push(node.left); // Push left child
if (node.right != null) stack1.push(node.right); // Push right child
}
while (!stack2.isEmpty()) {
result.add(stack2.pop().val); // Process nodes in reverse order
}
return result;
}
}2. Visited Flag Method
A single stack is used, and nodes are processed only after both subtrees are visited. A pointer to the previously visited node ensures the correct order.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.peek();
// If traversing down the tree
if (prev == null || prev.left == current || prev.right == current) {
if (current.left != null) {
stack.push(current.left);
} else if (current.right != null) {
stack.push(current.right);
}
}
// If traversing up from the left subtree
else if (current.left == prev) {
if (current.right != null) {
stack.push(current.right);
}
}
// If traversing up from the right subtree
else {
result.add(current.val);
stack.pop();
}
prev = current;
}
return result;
}
}Key Insights
1. Order Reversal in Two-Stack Method
• The two-stack method reverses the traversal order, taking advantage of the fact that postorder is the reverse of a specific preorder traversal (“root → right → left”).
• This approach simplifies handling the order at the cost of using additional space.
2. Tracking Visits in the Visited Flag Method
• The visited flag approach avoids an extra stack by carefully managing the traversal order.
• The pointer to the previously visited node ensures that the root is processed only after both subtrees are visited.
Morris Traversal: Space-Efficient Postorder Traversal
Postorder traversal is typically implemented using recursion or a stack, both of which require O(h) space, where h is the height of the tree. However, Morris Traversal offers a space-efficient alternative, enabling postorder traversal in O(1) space by temporarily modifying the tree structure. This technique is a powerful optimization for situations where memory usage is a critical constraint.
How Morris Traversal Works
Morris traversal eliminates the need for a recursion stack or explicit stack by using the right pointers of the tree nodes as temporary “threads” to traverse the tree. This ensures that the traversal does not lose track of unvisited nodes while processing others.
Key Idea:
1. Use the tree’s own structure by creating temporary links (threads) to traverse the tree without additional space.
2. Restore the tree to its original form after traversal.
Steps for Postorder Traversal:
1. Initialize a Dummy Node:
• A dummy node is created to serve as a placeholder parent of the root, simplifying edge cases.
2. Traverse the Tree:
• Move through the tree using the left children.
• Find the rightmost node in the left subtree (predecessor) to create a temporary thread back to the current node.
3. Process Nodes in Reverse:
• Reverse the path of nodes between the current node and its predecessor to process them in reverse order.
• Restore the tree structure by removing the temporary thread.
4. Move to the Right Subtree:
• Once the left subtree has been processed, move to the right subtree and repeat.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode curr = dummy, pred = null;
while (curr != null) {
if (curr.left != null) {
// Find the predecessor (rightmost node in the left subtree)
pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
// Create a thread to the current node
pred.right = curr;
curr = curr.left;
} else {
// Process nodes between curr.left and pred in reverse order
reverseAndAddNodes(curr.left, pred, result);
pred.right = null; // Remove the thread
curr = curr.right;
}
} else {
curr = curr.right;
}
}
return result;
}
// Helper method to reverse and add nodes between 'from' and 'to'
private void reverseAndAddNodes(TreeNode from, TreeNode to, List<Integer> result) {
List<Integer> temp = new ArrayList<>();
TreeNode curr = from;
while (curr != to) {
temp.add(curr.val);
curr = curr.right;
}
temp.add(to.val);
// Add nodes in reverse order to the result
Collections.reverse(temp);
result.addAll(temp);
}
}Key Points to Remember
1. Temporary Tree Modification:
• Threads are created using the right pointers of the tree but are removed after traversal to restore the tree.
2. Efficiency:
• Time Complexity: O(n), as each node is visited a constant number of times.
• Space Complexity: O(1), as no extra data structures are used.
3. When to Use Morris Traversal:
• Ideal for memory-constrained environments where space efficiency is critical.
• Useful for very large trees where the call stack in recursion might overflow.
Conclusion
Mastering postorder traversal techniques—recursive, iterative, and Morris—is crucial for solving tree-related problems efficiently. The recursive approach is simple and intuitive, the iterative method provides better control for large trees, and Morris traversal optimizes space usage to O(1). Understanding these techniques equips you to handle a wide range of challenges, from coding interviews to real-world applications.
