Postorder Traversal in Binary Trees

Tree traversal is the process of visiting every node in a tree exactly once in a systematic way. There are several types of tree traversals:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Level Order Traversal

In this blog, we'll focus on postorder traversal, its concept, and its implementation using both recursive and iterative approaches.

Understanding Postorder Traversal

Postorder traversal follows the order:

1. Visit the left subtree.
2. Visit the right subtree.
3. Visit the root node.

For example, consider the following binary tree:

                3
               / \
              4   5
             / \   \
            6   7   8
        

In postorder traversal, the nodes will be visited in the following order: 6, 7, 4, 8, 5, 3.

Recursive Approach

The recursive approach for postorder traversal is simple and uses the concept of recursion to visit nodes in the order Left → Right → Root.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Recursive Postorder Traversal
def postorder_recursive(root):
    if root:
        postorder_recursive(root.left)  # Traverse left subtree
        postorder_recursive(root.right)  # Traverse right subtree
        print(root.value, end=" ")   # Process root

# Example Usage
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(4)
    root.right = TreeNode(5)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(8)

    print("Postorder Traversal (Recursive):")
    postorder_recursive(root)
        

Iterative Approach

The iterative approach uses two stacks to mimic the recursive traversal. It helps when recursion is not allowed or when stack overflow issues might occur for large trees.

# Iterative Postorder Traversal
def postorder_iterative(root):
    if not root:
        return
    
    stack1, stack2 = [], []
    stack1.append(root)

    while stack1:
        current = stack1.pop()
        stack2.append(current)

        if current.left:
            stack1.append(current.left)
        if current.right:
            stack1.append(current.right)

    # Process the nodes in stack2
    while stack2:
        current = stack2.pop()
        print(current.value, end=" ")

# Example Usage
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(4)
    root.right = TreeNode(5)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(8)

    print("\nPostorder Traversal (Iterative):")
    postorder_iterative(root)
        

Conclusion

Both recursive and iterative approaches to postorder traversal are essential to understand as they cater to different use cases. The recursive method is easier to implement and intuitive, while the iterative method helps to avoid stack overflow issues in large trees.

Let us know which approach you prefer in the comments! Stay tuned for our next post on level order traversal.