Preorder traversal without recursion

Preorder traversal without recursion

Non recursive Inorder and postorder traversal without recursion of binary search tree are discussed earlier in detail. Let’s discuss preorder traversal without recursion for binary search tree.  In preorder traversal of BST, root node is traversed first, followed by left child and then right child. Let’s understand how preorder traversal of binary tree works. In below 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.
preorder traversal without recursion

Preorder traversal recursive implementation

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

Why to bother about iterative solution when we have simple recursive solution? Answer lies in thinking big or at scale. Memory overheads can be easily overlooked when number of nodes in tree is very small but not when tree is too big with millions of nodes. When tree has million nodes and to make things worse, tree is skewed. What will be stack depth when you use recursion? Yes, it will be in proportion of millions.

Each stack frame takes some bytes. System stack has a limit up to which it can grow. So, we risk outgrowing stack, causing stack overflow. In this case, better to depend on iterative method. Question arises that in iterative implementation of preorder traversal, stack is used. Then what is the difference? Difference is where stack is allocated. In iterative method, stack is implemented by program and memory is allocated on heap. Heap memory is large compared to stack memory for a process. Moreover, stack used by program stores less data onto stack as compared to function calls. 

Preorder traversal without recursion : Implementation

Now it is clear that why iterative method is needed, let’s focus on how iterative preorder traversal of tree can be implemented.

In preorder traversal root node is visited first, so when root is encountered first, mark it as visited too. Next node to be visited is left child of root. If there is a left child, go and visit it and that makes left child as current node. This goes on till there is left child.

What happens where left child of node is NULL. At this point, node and its left child is visited, only right child needs to be visited.
Take right child of node and follow the same process again. Once whole of right subtree of node is traversed, take the next node which needs to be processed. How to find next node to be processed.

It is clear that we go down, process left tree and come back and process right subtree, that means we keep track of node which needs to be processed next while moving down left. Node which is to be processed next once root is done is left child and followed by right child. Store left and right child onto stack, and since left is needed first, push order will be right child and then left child.
Final algorithm for preorder traversal without recursion

1. Start from root and push on to stack 
2. Pop from stack and print the node.
3. Push right child onto to stack.
4. Push left child onto to stack. 
5. Repeat Step 2 to 5 till stack is not empty.

Let’s taken example and go through it.
preorder traversal without recursion example

Non-recursive preorder traversal of binary search tree

#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 preorderTraversalWithoutRecursion(Node *root){
	stack ms;
	ms.top = -1;
 
	if(!root) return ;
 
	Node *currentNode = NULL;
	/* Step 1 : Start with root */
	push(&ms,root);
 
	while(!isEmpty(ms)){
		/* Step 5 : Pop the node */
		currentNode = pop(&ms);
		/* Step 2 : Print the node */
		printf("%d  ", currentNode->value);
		/* Step 3: Push right child first */
		if(currentNode->right){
			push(&ms, currentNode->right);
		}
		/* Step 4: Push left child */
		if(currentNode->left){
			push(&ms, currentNode->left);
		}
	}
}
 
 
void preorder (Node *root){
	if ( !root ) return;
 
 	printf("%d ", root->value );
	preorder(root->left);
	preorder(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);
    }
    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);

        preorder(root);
        printf("\n");

        preorderTraversalWithoutRecursion(root);
        return 0;
}

Complexity of preorder traversal without recursion of binary search tree is O(n) as each node of tree is visited at least once.

Please share if there is something wrong or missing. If you are interested in contributing to website, please contact us and earn.