Post-Order Traversal

Post-Order Traversal

We have covered Pre-Order (Root first) and In-Order (Root in the middle).

Now, it is time to explore Post-Order Traversal, where the Root is visited absolutely last!

1. What is Post-Order Traversal?

Tree traversal means visiting every single node in the tree exactly one time.

Because trees are hierarchical, we need a specific, repeatable path to follow.

Post-Order Traversal follows this strict path:

1. Left: First, recursively visit the entire Left subtree.
2. Right: Second, recursively visit the entire Right subtree.
3. Root: Third, visit the current node (the Root of the subtree).

The prefix "Post" helps you remember that the Root is visited after both of its children have been fully processed!

Post-Order Traversal: Children are always processed before their parents.

2. A Step-by-Step Example

Let's look at the tree in the diagram above and trace the exact execution path.

Assume we have a Binary Tree with a Root of 10, a Left Child of 5, and a Right Child of 15. The 5 has its own children: 2 (Left) and 7 (Right). The 15 has its own children: 12 (Left) and 20 (Right).

Step 1: Dive to the Bottom Left

• Start at the absolute Root: 10.
• Rule 1 says: Go Left. We move to 5.
• Rule 1 says: Go Left. We move to 2.
• Rule 1 says: Go Left. Node 2 has no left child!

Step 2: Processing the First Leaf

• We are at 2. Left is done.
• Rule 2 says: Go Right. No right child!
• Rule 3 says: Visit the Root. We print 2.
• Node 2 is fully processed. We move back up to 5.

Step 3: The Right Child of 5

• We are back at 5. Its Left child is fully processed.
• Rule 2 says: Go Right. We move to 7.

Step 4: Processing the Second Leaf

• We are at 7. Go Left? None.
• Go Right? None.
• Rule 3 says: Visit the Root. We print 7.
• Node 7 is done. We move back up to 5.

Step 5: Processing Node 5

• We are back at 5. Left (2) and Right (7) are both fully processed.
• Rule 3 says: Visit the Root. We print 5.
• Node 5 is done. We move back up to 10.

Step 6: Diving Down the Right Side

• We are back at 10. Its entire Left subtree is fully processed.
• Rule 2 says: Go Right. We move to 15.
• Rule 1 says: Go Left. We move to 12.

Step 7: Processing the Right Leaves

• At 12, no Left and no Right child. Visit Root: print 12. Move up to 15.
• At 15, Left is done. Rule 2: Go Right. We move to 20.
• At 20, no Left and no Right child. Visit Root: print 20. Move up to 15.

Step 8: Finishing the Tree

• At 15, Left and Right are done. Visit Root: print 15. Move up to 10.
• At 10, Left and Right are done. Visit Root: print 10.

Final Output: 2, 7, 5, 12, 20, 15, 10

3. Why Use Post-Order Traversal?

Every traversal has a specific superpower. What is Post-Order good for?

1. Deleting a Tree Safely If you want to delete an entire tree from memory, you cannot delete a parent node first, or you will lose the pointers to its children! Post-Order traversal guarantees that you will delete the Left child, then the Right child, and finally the Parent. It is the safest way to dismantle a tree.

2. Postfix Notation (Reverse Polish Notation) In mathematical expression trees, Post-Order traversal generates Postfix Expressions (like A B +). This is how many advanced calculators and computer systems evaluate math under the hood!

3. Calculating Directory Sizes If you want to know the total size of a folder on your computer, the OS must first calculate the size of every file and sub-folder inside it before it can tell you the total size of the parent folder. This is a classic Post-Order operation.

4. Code Example (Python)

Let's write the code for Post-Order Traversal.

Once again, we use Recursion. Notice how the print() statement is placed at the very end of the function, after both recursive calls!

# 1. Create the Node Class
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

# 2. Define the Post-Order function
def postorder_traversal(node):
    # Base case: If the node is None, stop!
    if node is not None:
        # 1. Traverse the Left Subtree
        postorder_traversal(node.left)
        # 2. Traverse the Right Subtree
        postorder_traversal(node.right)
        # 3. Visit the Root (Print it last!)
        print(node.data, end=" ")
# 3. Build the Binary Tree
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.left = Node(12)
root.right.right = Node(20)
# 4. Run the Algorithm
print("Post-Order Output:")
postorder_traversal(root)

5. Time and Space Complexity

• Time Complexity: O(n). Every single node in the tree is visited exactly once. The amount of time taken scales linearly with the number of items.
• Space Complexity: O(h). Where h is the maximum height of the tree. This extra space is required to maintain the recursive Call Stack.