Post-order binary tree traversal is a technique used to visit all the nodes of a binary tree in the following order: First, all nodes in the left subtree of root node are visited in post-order fashion, then all the nodes in the right subtree of root node are visited in post-order fashion, and finally the root node of the current tree is visited. The animated examples discussed in the next section will make the definition more clear.
Animation of Post-Order Binary Tree Traversal
Let’s consider the below binary tree and apply the post-order tree traversal technique:
Node A is the root node of the binary tree. Before we visit this node, we need to visit all nodes under it’s left and right subtrees in post-order fashion. Visited nodes will be coloured in green.
First we need to visit all the nodes under the left subtree of node A i.e., subtree with root as node B in post-order fashion. We apply the post-order logic again i.e, first visit all nodes in left subtree under node B, then visit all nodes in right subtree under node B, and finally visit the subtree’s root node (B). Left subtree of node B contains a singe node D so we just visit that node, then visit node E and finally visit the subtree’s root node B,
Now that all the nodes under the left subtree of node A are visited, we need to visit all nodes under the right subtree of node A in post-order fashion.
Finally the root node can be visited.
This is the order in which we visited all the nodes: D, E, B, F, G, C, A.
Recursive Implementation
Below is the implementation of a function which takes in the root node of a binary tree and traverses all the nodes in Post-Order fashion. It uses recursion technique which is much simpler and straightforward than the iterative version.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def post_order_traversal(node):
# Base case: if the node is None, return
if node is None:
return
# Step 1: Traverse the left subtree recursively
post_order_traversal(node.left)
# Step 2: Traverse the right subtree recursively
post_order_traversal(node.right)
# Step 3: Visit the current node
# Print its value or perform any other operation
print(node.value, end=" ")
# Create a sample binary tree
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Post-order traversal usage
if __name__ == "__main__":
tree_root = create_binary_tree()
print("Post-Order Traversal:")
post_order_traversal(tree_root)
Iterative Implementation
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def iterative_post_order_traversal(root):
if root is None:
return
# Initialize a stack for traversal
stack = [root]
# Use "Set" to store visited nodes
visited = set()
while stack:
# Peek the top element of the stack
current = stack[-1]
# Traverse left child if it exists and not visited
if current.left and current.left not in visited:
stack.append(current.left)
# Traverse right child if it exists and not visited
elif current.right and current.right not in visited:
stack.append(current.right)
else:
# If both children are visited or they don't exist,
# visit current node
node = stack.pop()
# Print the node's value (or perform desired operation)
print(node.value, end=" ")
# Add the node to the visited set
visited.add(node)
# Create a sample binary tree
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Let's now test Iterative post-order function
if __name__ == "__main__":
tree_root = create_binary_tree()
print("Iterative Post-Order Traversal:")
iterative_post_order_traversal(tree_root)