#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;
}
};
void create(node* &root){
int d;
cin>>d;
root=new node(d);
string left,right;
cin>>left;
if(left=="true"){
//cin>>d;
//root->left=new node(d);
create(root->left);
}
cin>>right;
if(right=="true"){
//cin>>d;
//root->right=new node(d);
create(root->right);
}
}
void level(node* root){
queue<node*>q;
q.push(root);
// cout<<"[[";
q.push(NULL);
int level=0;
vectortemp;
temp.push_back(root->data);
while(!q.empty()){
node* f=q.front();
// cout<<"[";
if(f==NULL){
// cout<<endl;
q.pop();
level++;
if(!q.empty()){
q.push(NULL);
// cout<<", [";
}
// if(level%2==0){
// reverse(temp.begin(),temp.end());
// }
// cout<<"[";
}
else if(level%2!=0){
// node* f=q.front();
// cout<< f->data<<" “;
q.pop();
// temp.push_back(root->data);
// cout<<level<<endl;
// node* p=q.front();
// if(p!=NULL){
// cout<<”, “;
// }
// cout<<”,"
if(f->left){
q.push(f->left);
temp.push_back(f->left->data);
}
if(f->right){
q.push(f->right);
temp.push_back(f->right->data);
}
}
else if(level%2==0){
// cout<< f->data<<" “;
// q.pop();
// cout<<level<<endl;
// node* p=q.front();
// if(p!=NULL){
// cout<<”, “;
// }
// cout<<”,"
if(f->left && f->right){
q.push(f->left);
temp.push_back(f->right->data);
}
if(f->right && f->left){
q.push(f->right);
temp.push_back(f->left->data);
}
// cout<< f->data<<" ";
q.pop();
}
}
// cout<<"]";
for(auto x:temp){
cout<<x<<" ";
}
}
int main(){
node* root=NULL;
create(root);
level(root);
return 0;
}
testcases not passed