Binary Search Tree : Level order printing

Print nodes of a tree in level order

Problem statement 

Print nodes of a 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

Analysis

This problem can be solved in two ways, in one way we need to maintain an auxiliary data structure to store nodes at a given level. Second way is to use recursion.

Let's see the second way first as this is easy to understand and implement.

Since we need to print nodes level wise, first thing we need to figure out is height of the tree. Once we have height, for every level print nodes. Second step can be implemented in recursive way, where we pass level as a parameter and at ever call we check if we have reached the given level, we print the node and return. 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 count every time we call print_level. When count becomes one, we print the node.

Algorithm

1. Find the height of the tree.

2. For each level print nodes as below.
3. Start from the root for each level.
4. Decrement the level count.
5. If level count is one, print the node.
6. Else move down the tree.

Code

#define MAX(a,b)  a>b ?a:b

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 MAX(lheight, rheight)+1;
}

void printTreeLevel(Node *root){

         int h = height(root);

         for(int i =1; i<=h+1; i++){

               printf("Level %d :", i)

               printTreeLevelRec(root, i);

               printf("\n);

         }

}

void printTreeLevelRec(Node * node, int desired){
        if(node == NULL)
                return;

        if (desired ==1)
                printf("%d", node->value);

        printTreeLevelRec(node->left, desired-1);
        printTreeLevelRec(node->right, desired-1);
}


Output for the tree given below is

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

Level 4 :12 

Algorithm of first approach

1. Start from the root

2. Add root to queue. 

3. Take the node out from the queue, and add left and right child of the root to queue.

4.  Print node and repeat step 3.

Code 

struct queue{

    struct node *element;

    struct queue *next;

};

typedef struct queue Queue;

void printLevel(Node * node){

 Queue *q =  NULL;

 enqueue(&q, node);

 while(!isEmpty(q)){

     Node *temp = front(q);

     printf("%d\n", temp->value);

     printf("adding left and right of %d\n" , temp->value);

     if(temp->left)

          enqueue(&q, temp->left);

     if(temp->right)

         enqueue(&q, temp->right);

     dequeue(&q);

 }

}

void enqueue(Queue **queue, Node * node){

        Queue *q  = NULL;

        Queue *head  = *queue;

        if(*queue == NULL){

                q =(Queue *)malloc(sizeof(Queue));

                q->element = node;

                q->next = NULL;

                *queue = q;

        }

        else{

                q = *queue;

                while(q->next)

                        q = q->next;

                Queue *temp =(Queue *)malloc(sizeof(Queue));

                q->next = temp;

                temp->element = node;

                temp->next = NULL;

                *queue = head;

        }

}

Node * front(Queue *queue){

        if(queue != NULL)

                        return queue->element;

}

void dequeue(Queue **queue){

        Queue *q = *queue;

        Node * node = q->element;

        Queue *temp = q;

        q = temp->next;

        temp = NULL;

        free(temp);

        *queue = q;

}

Output for the tree in the tree given below will be

30

adding left and right of 30

20

adding left and right of 20

40

adding left and right of 40

10

adding left and right of 10

37

adding left and right of 37

45

adding left and right of 45

12

adding left and right of 12

Complexity analysis

Since we would be traversing each node of the tree, time complexity would be of order N i.e.O(N).
In the first case, since we would be traversing N for every level we print, so complexity comes O(NlogN).