Postorder Traversal
Overview
Postorder Traversal is a variation of Tree DFS where the root is processed strictly AFTER its children: Left Child -> Right Child -> Root (Self).
This guarantees that you never process a parent node until both its left and right subtrees have been completely evaluated and processed.
This makes Postorder the mandatory choice for deleting a tree (you cannot safely delete a parent until you have successfully deleted all of its children, otherwise you orphan them and leak memory in languages like C++) or evaluating mathematical expression trees (you must evaluate 5+3 before you can multiply the result by 2).
Syntax
public class Postorder {
static class TreeNode {
int val; TreeNode left, right;
}
public void postorder(TreeNode root) {
if (root == null) return;
// 1. Go completely down the Left side
postorder(root.left);
// 2. Go completely down the Right side
postorder(root.right);
// 3. Process the Root (Self) LAST
System.out.print(root.val + " ");
}
}Common Pitfalls
- The iterative approach is notoriously difficult. While recursive Postorder is trivial, writing an iterative Postorder traversal using Stacks is one of the hardest basic algorithms, often requiring two stacks or a complex state machine to remember if you are returning from the left or right child.
Interview Questions
If you delete the parent node first (Preorder), you lose the pointers to the left and right children, stranding them in memory forever. Postorder guarantees you safely delete the leaves first, working your way up to the root.
Real-World Example
Safely deleting nodes and cleaning up resources. Even in Java where Garbage Collection exists, if tree nodes hold open network sockets, file handles, or heavy native memory objects, you want to explicitly close them from the bottom up to ensure clean teardown.
class ResourceNode {
ResourceNode left, right;
void closeResources() { /* free memory */ }
}
public class SystemCleanup {
public void teardown(ResourceNode root) {
if (root == null) return;
// Teardown dependencies first
teardown(root.left);
teardown(root.right);
// Finally, close the parent
root.closeResources();
}
}Check Your Knowledge
Test your understanding of Postorder Traversal with these quick questions.