# 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 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)
else

return node;
}
/* Driver program for the function written above */
int main(){
Node *root = NULL;

//Creating a binary tree

printTreeLevel(root);
return 0;
}

```

Output for the tree given below is

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

```
#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;

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;
}
}

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)
else

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

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

• http://www.blogger.com/profile/18128727745386306334 kuldeep singh

void printTreeLevelRec(Node * node, int desired)

do you think your above function would work properly..
what if “desired” will be 0 or negative value….do’nt you think your base condition of recursion is not able to handle this.

• http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

Hi Kuldeeep,
Thanks for commenting.
“desired” is from 1 to h+1 in the calling function. Hence it wont be equal to zero in any case. And as desired ==1 condition is already present, things should work fine.

• http://www.blogger.com/profile/13239744440447564585 Amber

If we use the recursion method wouldn’t the complexity be more than O(n) i.e O(nlgn)
as for every level we are going to that level and printing the values.

• http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

HI Amber,
Agreed, i would correct it. Thanks for pointing it out.