How to Implement Postorder Traversal of a Binary Tree in Python
Postorder traversal is one of the three fundamental depth-first traversal techniques for binary trees. It follows the Left ā Right ā Root pattern: the left subtree is visited first, then the right subtree, and finally the current node is processed.
This traversal order is particularly important for tasks like deleting a tree (children must be deleted before the parent), evaluating postfix expressions, computing directory sizes (subtrees before the parent folder), and generating postfix notation from expression trees.
In this guide, you will learn how postorder traversal works step by step, implement it recursively in Python, and understand its time and space complexity.
How Postorder Traversal Worksā
The traversal follows three rules applied recursively at every node:
- Traverse the left subtree (recursively apply postorder traversal).
- Traverse the right subtree (recursively apply postorder traversal).
- Visit the current node (process its data; for example, print it).
The key distinction from other traversals is that the root is visited last, which means after both subtrees are fully processed.
Step-by-Step Walkthroughā
Consider the following binary tree:
1
/ \
2 3
/ \ \
4 5 6
Here is how postorder traversal processes each node:
| Step | Action | Explanation |
|---|---|---|
| 1 | Go left from 1 ā 2 ā 4 | Keep going left until there is no left child |
| 2 | Visit 4 | Node 4 has no children, so we process it |
| 3 | Go right from 2 ā 5 | Move to right child of 2 |
| 4 | Visit 5 | Node 5 has no children, so we process it |
| 5 | Visit 2 | Both subtrees of 2 are done, so now process 2 |
| 6 | Go right from 1 ā 3 ā (no left child) ā 6 | Move to right subtree, then right child of 3 |
| 7 | Visit 6 | Node 6 has no children, so we process it |
| 8 | Visit 3 | Right subtree of 3 is done, so we process 3 |
| 9 | Visit 1 | Both subtrees of root are done, so we process root last |
Traversal result: 4 ā 5 ā 2 ā 6 ā 3 ā 1
The Algorithmā
The recursive algorithm is simple and elegant:
Postorder(node):
1. If node is None, return (base case)
2. Postorder(node.left) (traverse left subtree)
3. Postorder(node.right) (traverse right subtree)
4. Process node (visit current node)
The base case (node is None) stops the recursion when we reach a leaf node's non-existent child.
Python Implementationā
Defining the Node Classā
Each node stores a data value and references to its left and right children:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Implementing the Postorder Traversal Functionā
def postorder_traversal(node):
"""Recursively perform postorder traversal: Left ā Right ā Root."""
if node is None:
return
# Step 1: Traverse the left subtree
postorder_traversal(node.left)
# Step 2: Traverse the right subtree
postorder_traversal(node.right)
# Step 3: Visit the current node
print(node.data, end=' ')
Complete Exampleā
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def postorder_traversal(node):
"""Recursively perform postorder traversal: Left ā Right ā Root."""
if node is None:
return
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.data, end=' ')
if __name__ == '__main__':
# Build the tree:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
print("Postorder traversal of binary tree:")
postorder_traversal(root)
Output:
Postorder traversal of binary tree:
4 5 2 6 3 1
Returning the Traversal as a Listā
In practice, you often need the traversal result as a list rather than printed output:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def postorder_to_list(node):
"""Return the postorder traversal as a list of values."""
if node is None:
return []
return (
postorder_to_list(node.left) +
postorder_to_list(node.right) +
[node.data]
)
# Build the tree:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
# We call the postorder_to_list function
result = postorder_to_list(root)
# Then search inside for results
print(result)
Output:
[4, 5, 2, 6, 3, 1]
The concatenation approach above creates many intermediate lists. For better performance on large trees, use an accumulator:
def postorder_to_list(node):
"""Efficiently collect postorder traversal into a list."""
result = []
def _traverse(n):
if n is None:
return
_traverse(n.left)
_traverse(n.right)
result.append(n.data)
_traverse(node)
return result
This avoids creating and merging intermediate lists, reducing overhead from O(nĀ²) to O(n).
More Examplesā
Example 1: Three-Node Treeā
A
/ \
B C
root = Node('A')
root.left = Node('B')
root.right = Node('C')
postorder_traversal(root)
Output:
B C A
Example 2: Left-Skewed Treeā
A
/
B
/
D
root = Node('A')
root.left = Node('B')
root.left.left = Node('D')
postorder_traversal(root)
Output:
D B A
Example 3: Five-Node Treeā
A
/ \
B C
/ \
D E
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
postorder_traversal(root)
Output:
D E B C A
Example 4: Empty Treeā
postorder_traversal(None)
An empty tree (root is None) produces no output because the base case returns immediately.
Why Postorder Traversal Mattersā
Postorder traversal is the natural choice when you need to process children before their parent:
- Deleting a tree: You must delete child nodes before the parent to avoid dangling pointers.
- Evaluating expression trees: Operands (leaves) must be evaluated before their operator (parent).
- Computing directory sizes: A folder's size depends on the sizes of all its subfolders and files.
- Generating postfix notation: Converting an expression tree to reverse Polish notation.
# Example: Compute the sum of all nodes (children before parent)
def tree_sum(node):
if node is None:
return 0
left_sum = tree_sum(node.left) # Left subtree sum
right_sum = tree_sum(node.right) # Right subtree sum
return left_sum + right_sum + node.data # Process root last
| Traversal | Order | Common Use Cases |
|---|---|---|
| Inorder | Left ā Root ā Right | Sorted output from BST, expression evaluation |
| Preorder | Root ā Left ā Right | Tree copying, serialization, prefix expressions |
| Postorder | Left ā Right ā Root | Tree deletion, postfix expressions, dependency resolution |
Time and Space Complexityā
| Aspect | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every node is visited exactly once, where n is the total number of nodes |
| Space (best case) | O(log n) | For a balanced tree, the recursion depth equals the tree height |
| Space (worst case) | O(n) | For a completely skewed tree (essentially a linked list), the recursion depth equals n |
The space complexity comes from the call stack used by the recursive function. Each recursive call adds a frame to the stack, and the maximum depth equals the height of the tree.
For very deep or skewed trees (for example, with 10,000+ nodes in a chain), Python's default recursion limit (usually 1,000) will cause a RecursionError. You can increase the limit with sys.setrecursionlimit(), but for very deep trees, consider using an iterative postorder traversal with an explicit stack.
Conclusionā
Postorder traversal is a fundamental binary tree algorithm that visits nodes in the Left ā Right ā Root order. Its recursive implementation in Python is concise, comprising only three lines of logic, and runs in O(n) time with O(h) space, where h is the tree's height.
The traversal is essential for operations where children must be processed before their parent, such as tree deletion, expression evaluation, and computing aggregate values.
For practical applications, prefer the accumulator-based approach when collecting results into a list, and consider iterative alternatives for very deep trees to avoid hitting Python's recursion limit.