#include <bits/stdc++.h>
using namespace std;

class node{
   public:
   int data;
   node* left;
   node* right;
   
   node(int d)
   {
      this->data=d;
      this->left=NULL;
      this->right=NULL;
   }
};

node* buildTree(node* root)
{
   cout<<"Enter the data: "<<"\n";
   int data;
   cin>>data;
   root = new node(data);
   if(data==-1) return NULL;
   
   cout<<"please enter the data for inserting left of "<<data<<endl;
   root->left=buildTree(root->left);
   cout<<"please enter the data for inserting right of "<<data<<endl;
   root->right=buildTree(root->right);
   return root;
}

void levelordertraversal(node* root)
{
   queue<node*> q;
   q.push(root);
   
   while(!q.empty())
   {
      node* temp=new node(q.front());
      q.pop();
      
      if(temp==NULL)
      {
         q.push(NULL);
         cout<<"\n";
      }
      else
      {
         cout<<temp->data<<" ";
         if(temp->left) q.push(temp->left);
         if(temp-right) q.push(temp->right);
      }
   }
}

void preorder(node* root)
{
   if(root==NULL) return;
   cout<<root->data<<" ";
   preorder(root->left);
   preorder(root->right);
}

void Inorder(node* root)
{
   if(root==NULL) return;
   preorder(root->left);
   cout<<root->data<<" ";
   preorder(root->right);
}

void postorder(node* root)
{
   if(root==NULL) return;
   preorder(root->left);
   preorder(root->right);
   cout<<root->data<<" ";
}

void buildFromLevelorder(node* root){
   queue<node*> q;
   cout<<"Enter data for root"<<endl;
   int data;
   cin>>data;
   root=new node(data);
   q.push(root);
   
   while(!q.empty())
   {
      node* temp=q.front();
      q.pop();
      
      cout<<"Enter left node for: "<<temp->data<<endl;
      int leftData;
      cin>>leftData;
      
      if(leftData!=-1){
         temp->left=new node(leftData);
         q.push(temp->left);
      }
      
      cout<<"Enter right node for: "<<temp->data<<endl;
      int rightData;
      cin>>rightData;
      
      if(rightData!=-1)
      {
         temp->right=new node(rightData);
         q.push(temp->right);
      }
   }
}


int main() {
   node* root=NULL;
   buildFromLevelorder(root);
   
// 	root=buildTree(root);
// 	cout<<"Levelordertraversal of tree:- \n";
// 	levelOrderTravesal(root);
// 	cout<<"print preorder: "<<preorder(root)<<"\n";
// 	cout<<"print Inorder: "<<Inorder(root)<<"\n";
// 	cout<<"print preorder: "<<postorderorder(root);
	
	return 0;
}