DSA Post-order Traversal
Post-order traversal visits the left subtree, then the right subtree, and finally the root, making it the safe order for deleting a tree or evaluating an expression.
What Is Post-order Traversal?
Post-order traversal is a depth-first strategy that processes nodes in left, right, root order. At each node, you first recursively traverse its entire left subtree, then its entire right subtree, and only after both are finished do you visit the node itself. A node's children - and everything beneath them - are always fully processed before the node.
That children-before-parent guarantee makes post-order the right tool whenever a node's own processing depends on results from its subtrees. It's the safe way to delete or free a tree, since every child is removed before its parent; it's how expression trees get evaluated, since an operator needs both operand values before it can compute anything; and it's how you'd compute a subtree's height or size, since those depend on the children's height or size first.
Recursive Post-order Traversal
Example: Recursive Post-order
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def postorder(node, result=None):
if result is None:
result = []
if node is None:
return result
postorder(node.left, result)
postorder(node.right, result)
result.append(node.value)
return result
# Tree: root 5; left child 3, right child 8.
# 3's children are 2 and 4; 8's children are 7 and 9.
root = Node(5,
Node(3, Node(2), Node(4)),
Node(8, Node(7), Node(9)))
print(postorder(root))
# [2, 4, 3, 7, 9, 8, 5]Iterative Post-order Traversal (Using Two Stacks)
Post-order is the trickiest of the three to write iteratively, because the root is visited last, not first. A simple trick fixes this: use one stack to explore the tree in root, right, left order (the mirror image of pre-order), pushing every node visited onto a second stack instead of a result list. Once the first stack is empty, popping the second stack from top to bottom yields exactly the left, right, root order that post-order requires.
Example: Iterative Post-order (Two Stacks)
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def postorder_iterative(root):
if root is None:
return []
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
return [node.value for node in reversed(stack2)]
root = Node(5,
Node(3, Node(2), Node(4)),
Node(8, Node(7), Node(9)))
print(postorder_iterative(root))
# [2, 4, 3, 7, 9, 8, 5]Example: Evaluating an Expression Tree
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def evaluate(node):
if node.left is None and node.right is None:
return node.value # leaf: a number
left_val = evaluate(node.left) # left subtree first
right_val = evaluate(node.right) # then right subtree
operator = node.value # root (operator) last
if operator == '+':
return left_val + right_val
if operator == '-':
return left_val - right_val
if operator == '*':
return left_val * right_val
if operator == '/':
return left_val / right_val
raise ValueError(f'Unknown operator: {operator}')
# Expression tree for (3 + 4) * (10 - 6)
tree = Node('*',
Node('+', Node(3), Node(4)),
Node('-', Node(10), Node(6)))
print(evaluate(tree)) # 28- Visit order is left subtree, then right subtree, then root
- Every node's children are fully processed before the node itself
- The safe order for deleting or freeing a tree, since children go first
- The natural traversal for evaluating expression trees and postfix notation
- Runs in O(n) time and O(h) extra space, where h is the tree's height
Exercise: DSA Tree Traversal
In in-order traversal of a binary tree, what is the visiting sequence?
