Level order traversal of Binary Search Tree

Level order traversal of Binary Search Tree

Level order traversal of a binary search tree is very commonly asked problem in interviews. The problem is to print nodes of a binary tree level wise i.e. nodes at same level should be printed together. For example, in following tree output should be 10,6,15,4,7,13,17
level order traversal of BST

Level order traversal of BST can be solved with two approaches. First one requires an auxiliary data structure to store nodes at a particular level. Second approach is to use recursion. Let’s see the second approach as it is easy to understand and implement.

Since we need to print nodes level wise, calculate number of levels given binary tree has. In worst case, number of level will be N and in best case it will be log N. Maximum number of levels a tree has is equal to height of tree. So, calculate height, traverse each level less than height and print nodes at that level. 

At every node, keep track of level on which that node is, in tree. Starting from the root, to height, level to be printed is incremented by one. From root, start with desired level let’s call it desiredLevel. As you move down, decrement level by one at each level. Once desiredLevel becomes 1, node is at correct level and hence print the node.

At every level, above step can be implemented recursively. Base case for recursion is evident from above discussion i.e when level is equal to 1, print node and return.  Otherwise, recurse with desiredLevel decremented by one.

For example in tree given above if we want to print nodes at level 2, we call function as print_level(root, 2)  and decrement level every time we call print_level. When count is equal to one, we print node.

Algorithm to print nodes in level order traversal

1. Find height ht of the tree.
2. For each level from level 0 to level ht
   2.1 If level count is one, print node.
   2.2 If not, then decrement level count.
   2.3 If there is left child, move down towards left subtree.
   2.4 If there is right child, move down towards right subtree.

Level order traversal implementation c

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
 
typedef struct node Node;
 
#define MAX(a,b)  a>b ?a:b
 
int height(Node *root){
    if(!root)
        return 0;
 
    if(!root->left && !root->right)
        return 1;
 
    int lheight = height(root->left);
    int rheight = height(root->right);
 
    return MAX(lheight, rheight) + 1;
}
 
void printTreeLevel(Node *root){
    int i = 0;
    int h = height(root);
 
    for(i=1; i<=h; i++){
        printf("Level %d :", i);
        printTreeLevelRec(root, i);
        printf("\n");
    }
}
 
void printTreeLevelRec(Node * node, int desired){
    if(!node)
        return;
    if (desired == 1)
        printf("%d ", node->value);
 
    printTreeLevelRec(node->left, desired-1);
    printTreeLevelRec(node->right, desired-1);
}
 
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);
 
    printTreeLevel(root);       
    return 0;
}

Output for the tree given below is
level order traversal example

 
Level 1 :30
Level 2 :20  40  
Level 3 :10 37 45
Level 4 :12

Iterative method to level order traversal of BST

In iterative approach, an auxiliary data storage is required to store nodes at the same level. Each node of tree enters into storage at least once and taken out from there and printed.
Whenever a node is taken out from storage, it’s left and right child nodes are inserted into storage at end.

In storage, nodes which are entered first are taken out first. or insertion is happening at rear and removal is done from front. Which data structure provides this property? Yes, Queues. To implement iterative version of solution, we will use a queue as auxiliary storage.

Below figure demonstrates complete algorithm for level order traversal using queue.
level order traversal


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
 
typedef struct node Node;
 
struct queue{
    Node *element;
    struct queue *next;
};
typedef struct queue Queue;
  
void enqueue(Queue **queue, Node *node){
	Queue *q  = NULL;
	Queue *head  = *queue;
 
	if(!(*queue)){
		q =(Queue *)malloc(sizeof(Queue));
		q->element = node;
		q->next = NULL;
		*queue = q;
	}
	else{
		q = *queue;
		while(q->next)
			q = q->next;
 
		Queue *currentNode =(Queue *)malloc(sizeof(Queue));
		q->next = currentNode;
		currentNode->element = node;
		currentNode->next = NULL;
		*queue = head;
	}
}
 
int isEmpty( Queue *q){
	if(!q) return 1;
 
	return 0;
}

Node *front(Queue *queue){
	if(queue)
		return queue->element;
}
 
void dequeue(Queue **queue){
	Queue *q = *queue;
 
	Queue *nodeToDelete = q;
	q = nodeToDelete->next;
	nodeToDelete = NULL;
	free(nodeToDelete);
 
	*queue = q;
}
 
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;
}
 
void printTreeLevel(Node * node){
 
 Queue *q =  NULL;
 enqueue(&q, node);
 
 while(!isEmpty(q)){
    Node *currentNode = front(q);
 
    printf("%d ", currentNode->value);
 
    if(currentNode->left)
     	enqueue(&q, currentNode->left);
    if(currentNode->right)
    	enqueue(&q, currentNode->right);
 
    dequeue(&q);
 }
}

/* 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);
 
    printTreeLevel(root);       
    return 0;
}

Since we would be traversing each node of the tree, time complexity of second method of level order traversing would be of order N i.e.O(N). This method as an added space complexity of O(N) because in worst case when tree is balanced, there will be N/2 nodes at last level which need to be stored in queue at the same time, hence space complexity of O(N).

In the first approach, we traverse root nodes log N times (log N is height of tree), nodes at level two for  log N – 1, level tree 3 for log N-2 times and so on, at the end nodes at level log N are traversed only once. Hence total number of nodes traversed = log N + log N -1 + log N -2 ….. + 1 = log N (log N -1 ) /2 = ( log N )2

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