Iterative Inorder traversal

One of the most common things we do on 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 recursive way. In this post, let’s focus on iterative implementation of inorder traversal or iterative inorder traversal without recursion.

Before solution, what is inorder traversal of 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]

iterative inorder traversal

Iterative inorder traversal without stack : Thoughts

As we go into discussion, one quick question : why recursive inorder implementation is not that great? 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 stack, eventually filling up all the space system has for stack. This problem is known as stack overflow.
When binary tree is skewed, that is when every node has only one child, recursive implementation may lead to stack overflow, depending on the size of tree. In production systems, we usually do not know upfront size of data structures, it is advised to avoid recursive implementations.

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

All these steps are easy to translate in iterative way. One thing needs to be thought of is : how to go to parent node? In inorder traversal, the last node visited before 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 node, we have to just look at the last visited node), stack is great candidate for it which has last in first out property.

Iterative inorder traversal : algorithm

  1. Start from the root, call it current .
  2. If current is not NULL, push current on to stack.
  3. Move to left child of current and go to step 2.
  4. If current  == NULL and !stack.empty(),  current = s.pop.
  5. Process current and set current = current.right, go to step 2.

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

iterative inorder traversal

We start with node(10), current = node(10). Current node is not null, put it on 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 left child, which in this case it is null. What to do now? As stack is not empty, pop last node added to it. current = node(1). Process node(1). Traversal  = [1]

Move to 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 left child of current node (14), which is node(12). current = node(12) which is not null, put it onto stack.

inorder traversal with recursion

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 stack.

Left child of node(15) is null, so we pop from stack. current = node(15). Process node(15). Fetch right child of 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]

Iterative inorder traversal : 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;
}

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 communications@algorithmsandme.com