Understanding iterative inorder traversal

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

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

Iterative Steps

Inorder traversal is recursive, as the first and last steps of traversal use inorder 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. Inorder traversal can be broken down into three iterative steps :

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

1. Traverse the node's left subtree

The first step of inorder traversal is to visit the left subtree using inorder 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.