zigzag traversal of binary search tree

zigzag traversal of binary search tree

In this post, let’s discuss a problem which is very similar to level order traversal of binary search tree.¬†However, there is a small difference between level order and zigzag traversal of binary search tree or spiral traversal. In zigzag traversal, at every level, direction of traversal of that level changes from left to right or right to left.

That is to say, printing levels, one level is printed left to right, second from right to left and then third, again from left to right.
Given a binary search tree, print all nodes of the tree in zigzag order. For example, for following tree, output should be : 30,40,20,15,25,37,45

zigzag traversal of binary search tree
zigzag traversal of binary search tree

We have already have solved for the level order printing of a tree, let’s use that knowledge and solve this problem. All that is different is the direction of traversal of levels. What if we can pass on hint for direction level to be traversed in? Well that solves our problem ūüôā

Zigzag traversal of tree : Recursive implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
#define MAX(a,b)  a>b ?a:b
 
struct node{
        int value;
        struct node *left;
        struct node *right;
};
typedef struct node Node;
 
int height(Node *root){
    if(root == NULL)
        return 0;
 
    if(!root->left && !root->right)
        return 1;
 
    int lheight = height(root->left);
    int rheight = height(root->right);
 
    return 1+ (MAX(lheight, rheight));
}
 
void zigzagTraversalRecursive(Node * node, int desired, int ltr){
  if(node == NULL) return;
 
   if (desired == 1)
      printf("%d  ", node->value);
      /* Based on the flag call the recursive function accordingly */
      if(ltr){
          zigzagTraversalRecursive(node->left, desired-1, ltr);
          zigzagTraversalRecursive(node->right, desired-1, ltr);
       }
       else{
          zigzagTraversalRecursive(node->right, desired-1, ltr);
          zigzagTraversalRecursive(node->left, desired-1, ltr);
       }
}
 
void spiralLevelOrderTraversal(Node *root){
    int h = height(root);
    int i;
    int ltr = 1;
    for(i=1; i<=h; i++){
      printf("\n Level %d :", i);
      /* initially passing it to left to right */
      zigzagTraversalRecursive(root, i, ltr);
      /* For next iteration (level), it will be reversed */
      ltr = !ltr;
      printf("\n");
    }
}
 
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;
        Node * last = NULL;
        Node *ptrToHead = 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);
 
        spiralLevelOrderTraversal(root);
        return 0;
}

In this implementation, we pass direction to each iteration of traversal. When level changes, flip the direction from left to right or right to left.

What is the complexity of algorithm? Well if height of BST is h, we traverse nodes as h*1 + (h-1)*2 + (h-2)*3…..1*n, which is quadratic in nature and hence, complexity of this method will be O(h *n2).¬†(Thanks Gopi for pointing out).

Another problem of solution is that it uses recursion and we know if depth of recursion is too deep, we may end up in trouble. It consumes system space and hence adds to space complexity of solution. 

What is the best way to replace recursion? Yes, use stacks.

Zigzag traversal of BST : Iterative implementation

In order to traverse BST using stack, we will have to use two stacks. In first stack, push right child first and then left child, so that while popping left child is popped first and then right child. Hence, order of nodes in this first stack is left to right.
In second stack, push left child first and then right child. Order of popped nodes is right to left.
To start with, put root in any of the one stack.

Algorithm to zig zag traverse a BST using stacks.<

1. Create two stacks S1 and S2. Push root into stack S1  
2. While any one of stacks is not empty, repeat below steps
   2.1 While S1 is not empty, pop top node, currentNode.
   2.2 Print currentNode->value 
   2.3 Push right child and left child of currentNode on stack S2.
   2.4.If S2 is not empty, pop top node, currentNode.
   2.5 Print currentNode->value 
   2.6 Push left child and right child of currentNode on S1.

Implementation is very simple. To understand how stack implementation in c, please go through below post  Stack Basics and implementation

Iterative implementation of zigzag traversal

#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 zigzagTraversal(Node * root){
	stack s1, s2;
	s1.top = -1;
	s2.top = -1;
 
	if(root == NULL ) return;
 
	push(&s1, root);
 
	while(!isEmpty(s1) || !isEmpty(s2)){
		printf("\n");
		while(!isEmpty(s1)){
			Node *currentNode = pop(&s1);
			printf("%d " , currentNode->value);
			if(currentNode->right)
				push(&s2, currentNode->right);
			if(currentNode->left)
				push(&s2, currentNode->left);
        }
        printf("\n");
        while(!isEmpty(s2)){
        	Node *currentNode = pop(&s2);
        	printf("%d " , currentNode->value);
        	if(currentNode->left)
        		push(&s1, currentNode->left);
        	if(currentNode->right)
        		push(&s1, currentNode->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);

        zigzagTraversal(root);
        return 0;
}

Complexity of iterative approach is O(N) why? Because we visit each node of tree only once. However, space complexity would be O( 2h-1).

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

  • http://about.me/tg9963 GOPI GOPINATH

    recursive zigzag traversal ll ve a worst case complexity of O(n^2) when the tree is a skewed tree.

    • http://algorithmsandme.in/ Jitendra Sangar

      Agreed, will correct it.

  • Pingback: Amazon interview experience 5 | Algorithms and Me()