//
//  main.cpp
//  BFS Binary Tree
//
//  Created by Himanshu on 26/08/21.
//

#include <iostream>
#include <queue>
using namespace std;

struct node {
    int value = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->value = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}

void BFS (Node *root) {
    if (root == NULL) {
        return;
    }
    queue<Node*> qu;
    qu.push(root);
    int level = 0;
    cout<<"Level order traversal:";
    while (!qu.empty()) {
        int size = (int) qu.size();
        cout<<endl<<"Level: "<<level<<endl;
        for (int i=0; i<size; i++) {
             Node* curr = qu.front();
             cout<<(curr->value)<<" ";
             qu.pop();
             if (curr->left) {
                 qu.push(curr->left);
             }
             if (curr->right) {
                 qu.push(curr->right);
             }
        }
        level++;
    }
    cout<<endl;
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(20);
    root->right = newNode(21);
    root->right->left = newNode(30);
    root->right->right = newNode(31);
    BFS (root);
    return 0;
}