#include<bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node *left;
node *right;
node(int d)
{
data=d;
left=NULL;
right=NULL;
}
};
node *build(string s)
{
if (s == “true”)
{
int d;
cin >> d;
node *root = new node(d);
string l;
cin >> l;
if (l == “true”)
{
root->left = build(l);
}
string r;
cin >> r;
if (r == “true”)
{
root->right = build®;
}
return root;
}
return NULL;
}
void LevelOrder(node *root)
{
deque<node *> q;
node *temp;
q.push_back(root);
cout<data;
int level=1;
while(!q.empty())
{
if(level%2==0)
{
temp=q.back();
q.pop_back();
if(temp->left!=NULL)
{
q.push_front(temp->left);
cout<<temp->left->data<<" ";
}
if(temp->right!=NULL)
{
q.push_front(temp->right);
cout<<temp->right->data<<" ";
}
level++;
}
else
{
temp=q.front();
q.pop_front();
if(temp->right!=NULL)
{
q.push_back(temp->right);
cout<<temp->right->data<<" ";
}
if(temp->left!=NULL)
{
q.push_back(temp->left);
cout<<temp->left->data<<" ";
}
level++;
}
}
return;
}
int main()
{
node *root=build(“true”);
LevelOrder(root);
}