One of the most common things we do on a binary tree is traversal. In Binary search tree traversals we discussed different types of traversals like inorder, preorder and postorder traversals. We implemented those traversals in a recursive way. In this post, let’s focus on the iterative implementation of inorder traversal or iterative inorder traversal without recursion.

Before the solution, what is an inorder traversal of a binary tree? In inorder traversal, visit left subtree, then root and at last right subtree. For example, for given tree, inorder traversal would be: [1,5,6,10,12,14,15]

## Inorder traversal iterative: Thoughts

As we go into discussion, one quick question: why recursive inorder implementation is not good? We know that recursion uses implicitly stack to store return address and passed parameters. As recursion goes deep, there will be more return addresses and parameters stored on the stack, eventually filling up all the space a system has for a stack. This problem is known as stack overflow.

When a binary tree is skewed, that is when every node has only one child, a recursive implementation may lead to stack overflow, depending on the size of the tree. In production systems, we usually do not know the upfront size of data structures, it is advised to avoid recursive implementations.

What are we essentially doing in recursive implementation? We check if the node is null, then return. If not, we move down the left subtree. When there is nothing on left subtree, we move up to the parent and then go to the right subtree.

All these steps are easy to translate in an iterative way. One thing needs to be thought of is: how to go to parent node? In inorder traversal, the last node visited before the current node is the parent node.

If we keep these nodes on some structure, where we can refer them back, things will be easy. As we refer the most recent node added to structure first (when finding parent of the node, we have to just look at the last visited node), Stack is a great candidate for it which has last in first (LIFO) out property.

**Algorithm**

- Start from the root, call it
`current`. - If
`current`is not NULL, push`current`on to stack. - Move to left child of
`current`and go to step 2. - If
`current`

== NULL and !stack.empty(),`current`

= s.pop. - Process
`current`and set`current`

=`current.right`

, go to step 2.

Let’s take an example and see how this algorithm works.

We start with node(10), current = node(10). Current node is not null, put it on the stack.

As there is left child of node(10), move current = current.left, so current = node(5), which is not null, put node on to stack.

Again, move down to left child of node(5), current = current.left = node(1). Put the node on to stack.

Again move down to the left child, which in this case it is null. What to do now? As the stack is not empty, pop last node added to it. current = node(1). Process node(1). Traversal = [1]

Move to the right child of node(1), which is null, in that case, pop from the stack and process the node, current = node(5). Traversal = [1,5]

Move to the right child of node(5) i.e. node(6). Push on to the stack.

Move down to left subtree, which is null, so pop from stack. current = node(6), process it. Traversal = [1,5,6]

Move to right child of node(6), which is null, so pop from stack current = node(10). Process the node. Traversal = [1,5, 6,10]

Get right child of node(10), which is node(14), current = node(14), as current is not null, put it on to stack.

Again move to the left child of the current node (14), which is node(12). current = node(12) which is not null, put it onto the stack.

Get left child of current node, which is null. So pop from stack, current = node(12). Process it. Traversal = [1,5,6,10,12]

Current node = current.right, i.e null, so pop out of stack. current = node(14). Process node(14). Traversal = [1,5,6,10,12,14]

Again current = current.right which is node(15). Put it back on to the stack.

The left child of node(15) is null, so we pop from stack. current = node(15). Process node(15). Fetch right child of the current node which is again null and this time even stack is already empty. So stop processing and everything is done. Traversal = [1,5,6,10,12,14,15]

### Implementation

#include <stdio.h> #include<stdlib.h> #include<math.h> struct node{ int value; struct node *left; struct node *right; }; typedef struct node Node; #define STACK_SIZE 10 typedef struct stack{ int top; Node *items[STACK_SIZE]; }stack; void push(stack *ms, Node *item){ if(ms->top < STACK_SIZE-1){ ms->items[++(ms->top)] = item; } else { printf("Stack is full\n"); } } Node * pop (stack *ms){ if(ms->top > -1 ){ return ms->items[(ms->top)--]; } else{ printf("Stack is empty\n"); } } Node * peek(stack ms){ if(ms.top < 0){ printf("Stack empty\n"); return 0; } return ms.items[ms.top]; } int isEmpty(stack ms){ if(ms.top < 0) return 1; else return 0; } void inorderTraversalWithoutStack(Node *root){ stack ms; ms.top = -1; Node *currentNode = root; while(!isEmpty(ms) || currentNode ){ if(currentNode){ push(&ms, currentNode); currentNode = currentNode->left; } else { currentNode = pop(&ms); printf("%d ", currentNode->value); currentNode = currentNode->right; } } } void inorder (Node * root){ if ( !root ) return; inorder(root->left); printf("%d ", root->value ); inorder(root->right); } Node * createNode(int value){ Node * temp = (Node *)malloc(sizeof(Node)); temp->value = value; temp->right= NULL; temp->left = NULL; return temp; } Node * addNode(Node *node, int value){ if(node == NULL){ return createNode(value); } else{ if (node->value > value){ node->left = addNode(node->left, value); } else{ node->right = addNode(node->right, value); } } return node; } /* Driver program for the function written above */ int main(){ Node *root = NULL; //Creating a binary tree root = addNode(root,30); root = addNode(root,20); root = addNode(root,15); root = addNode(root,25); root = addNode(root,40); root = addNode(root,37); root = addNode(root,45); inorder(root); printf("\n"); inorderTraversalWithoutStack(root); return 0; }

The complexity of iterative implementation of inorder traversal is `O(n)` with worst-case space complexity of `O(n)`.

Please share if there is something wrong or missing. If you want to contribute an share your knowledge with thousands of learners across the world, please reach out to [email protected]