# Post Order Traversal of Binary Tree Nodes

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

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

``````