Inorder traversal without recursion

Inorder traversal without recursion

In today’s post, we will discuss inorder traversal without recursion and using stack. Tree traversals and problems based on them are very commonly asked in programming interviews and most of the time, interviewer asks you to implement the same solution without recursion.
If you are looking for solution inorder traversal without stack or recursion, please go to the link.

First of all, what is tree traversal? Tree traversal is a process of visiting all nodes of tree once. Since tree are recursive structure, any tree traversal can be done by dividing traversal in three parts:

Traverse left subtree, traverse root, traverse right subtree.

Order of traversal of these three parts may not necessarily be same. In fact, order of these three steps decides type of traversal being done on tree.
If root is traversed before left and right subtree, it is called preorder traversal.
If root is traversed after left subtree but before right subtree, it is called inorder traversal.
And finally if root is traversed after left and right subtree, it is called as postorder traversal.

Inorder traversal without recursion

Let’s understand how inorder traversal of binary tree. In animation, four colors are used
Red : To mark non visited nodes of tree
Purple: Node on stack.
Green: Node being considered at any point of time. This node will be moved to stack.
Yellow: Node which is visited. This state will always come after purple color. See the animation.

Inorder traversal without recursion

Traversal problem can be solved using recursion. Any traversal inorder, preorder, or postorder can be written in three lines of code using recursion.It becomes a bit complicated when we don’t need to use system stack and avoid recursion, all in all we want to replace system stack with application stack.

Inorder traversal of binary tree: Recursive implementation

void inorder(Node *root){
     if(root){
          inorder(root->left);
          printf("%d", root->data);
          inorder(root->right);
     }
}

Now coming back to problem, implementing inorder traversal without using recursion. What would be the best data structure to replace recursion? Answer is stack! Implementation of tree traversals without recursion involves stack.

When recursive solution is simple to implement, then what is need of iterative solution for inorder traversal or any other traversal? As it is known that recursive implementations have stack memory overhead where stack frames are used to stored call sequence and their parameters. When trees are small and balanced, it is not bad to use recursion, worst case space complexity will be O(log n).
What if tree is large with millions of nodes in it and completely skewed. Then recursive implementation will store a million stack frames before it starts rewinding. To avoid this we need iterative method, although it will also use stack but it will store only 4 bytes and not a huge data which is usually stored on system stack when a function calls another function.

Inorder traversal without recursion algorithm

1. Start from root, let's call it currentNode.
2. If current is not NULL, push the node on to stack.
3. Move to left child of current, currentNode=currentNode->left.
  3.1 Go to step 2.
4. If current is NULL and stack is not empty, pop node from the stack.
5. Print node value
6. Move to right child of current, currentNode=currentNode->right
   6.1 Go to step 2.

inorder traversal without recursion example

Inorder traversal without recursion 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 inorderTraversalWithoutRecursion(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 * newNode =  (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;
    return newNode;
}

Node * addNode(Node *node, int value){
    if(!node) return createNode(value);
    
    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");
        inorderTraversalWithoutRecursion(root);

        return 0;
}

This is simplest traversal to implement with stack. binary search tree

Let see the execution trace of inorder traversal without recursion and understand better using example tree :
When function inorderTraversalWithoutRecursion() is called for first time, root pointer of tree is available, that is pointer to node 6. Assign it to temporary variable currentNode.

If stack is empty or currentNode is not NULL, enter in while loop.

In loop, check if currentNode is not NULL. If currentNode is not null, need to traverse left subtree currentNode first, and then visit currentNode. So, how to save currentNode (6)? Put it on stack. Stack = [6].
Change currentNode to currentNode’s left which is 3. No else part is executed.

Coming back to while loop, stack is not empty, enter loop, currentNode (now 3) is null? No. Put node 3 on stack, stack = [6,3]. Move to left currentNode, to node 2. No else part executed.

Same procedure is repeated for node 2, put it on stack, stack = [6,3,2].

While loop again, now currentNode is null. Since stack is not empty, enter while loop.
As currentNode is null, go to else statement. Pop element from stack, which is 2 and print it. Output = [2].

Now, assign currentNode to right child of node popped from stack, which is null in this case.

While loop is entered again as stack is not empty yet, currentNode is null and hence we execute else statement, pop element from stack and print it. Output = [2,3].

Assign currentNode to right child of node 3 which is 5.

Enter while loop and this time currentNode is null, push it on stack and move left. Stack= [6,5].

While loop continues as stack is not empty. As 5 has no left child, currentNode is null, pop element from stack and print it, Output = [2,3,5].

Assign currentNode as right child of 5 which is null, in next iteration of while loop, else part is executed, pop element from stack and print it. Output = [2,3,5,6]

Again, currentNode assigned as right of currentNode (8). Stack is empty but currentNode is not null, hence enter loop. If condition is true, push node on stack. Stack = [8]. Assign currentNode left child of 8, which is 7.

CurrentNode is not null, push 7 on stack. Stack = [8,7] and move currentNode to left of it which is null.

In this case,else block is executed, pop element from stack and print it. Output = [2,3,5,6,7].

Make currentNode as right child of node 7 which is again null. So, pop element from stack and print it. Output =[2,3,5,6,7,8]. And move to right of 8 which is node 9.

Even stack is empty, currentNode is not null, enter while loop, and push node on stack.
Stack = [9].
Move currentNode to left of currentNode, which is null.

While loop is entered and else blocked is executed. Pop element and print it. Output = [2,3,5,6,7,8,9].

Move to right of node 9 which is null. At this point stack is empty and currentNode is also null, hence while loop exits.

Complexity of implementation is O(N) of inorder traversals without recursion

Preorder and postorder traversal visit :
Post order traversal of binary search tree without recursion
Preorder traversal of tree without recursion

Please share if there is something missing or wrong. If you want to contribute to algorithms and me, please contact us.