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)
```