Print a binary tree level by level with each level printed on a new line.

Solution# 1: The regular BFS algorithm doesn't keep a track of the level it is on. We will modify it to keep a track of the current level. Below is the code,

Input Tree:
           6
         /    \
       4      8
     /   \       \
    1    5      9

Output:
6
4 8
1 5 9

void printLevel(struct node* root)
{
    queue q;

    q.push(root);
    q.push(NULL);

    while(q.front() != NULL)
    {
        struct node* temp = q.front();
        q.pop();

        while(temp != NULL)
        {
            printf("%d ", temp->data);

            if(temp->left != NULL)
                q.push(temp->left);

            if(temp->right != NULL)
                q.push(temp->right);

            temp = q.front();
            q.pop();
        }
        
        printf("\n");

        q.push(NULL);
    }
}