Understanding iterative postorder traversal

Just like preorder and inorder traversal, to understand the iterative implementation of postorder traversal, we need to split the whole process into small steps and understand how each step functions. Let us start by looking at how postorder traversal is done.

Algorithm

• Step 1: Recursively traverse the node's `left` subtree.
• Step 2: Recursively traverse the node's `right` subtree.
• Step 3: Visit the node.

Iterative Steps

Postorder traversal is recursive, as the first and second steps use postorder traversal again. Let us now look at the distinct iterative steps this traversal follows and how we can implement these steps. Once we have implemented these individual steps, we can glue them together to create an iterative algorithm for the entire traversal. Postorder traversal can be broken down into three iterative steps :

• Step 1: Traverse the node's `left` subtree.
• Step 2: Traverse the node's `right` subtree.
• Step 3: Visit the node.

To create an iterative algorithm, we will first follow these steps sequentially. The complete algorithm will make sense when we combine all these steps and consider the big picture.

1. Traverse the node's left subtree

The first step of postorder traversal is to traverse the left subtree using postorder traversal. Following this definition, for a tree rooted at node R, we start from the node R and then keep going left until we reach a null. We stop at null because there is nowhere to go beyond that. Let's say this null was the left child of node N.