#include<iostream>
#include<algorithm>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int d){
data=d;
left=NULL;
right=NULL;
}
};
node* buildtree(string s){
if(s=="true"){
int d;
cin>>d;
node*root=new node(d);
string l;
cin>>l;
if(l=="true"){
root->left=buildtree(l);}
string r;
cin>>r;
if(r=="true"){
root->right=buildtree(r);
}
return root;
}
return NULL;
}
void printkthlevel(node* root,int k){
if(root==NULL){
return;
}
if(k==1){
cout<<root->data<<" ";
return;
}
printkthlevel(root->left,k-1);
printkthlevel(root->right,k-1);
return;
}
void printkthlevelreverse(node* root,int k){
if(root==NULL){
return;
}
if(k==1){
cout<<root->data<<" ";
return;
}
printkthlevel(root->right,k-1);
printkthlevel(root->left,k-1);
return;
}
int height(node* root){
if(root==NULL){
return 0;
}
int ls=height(root->left);
int rs=height(root->right);
return 1+max(ls,rs);
}
void levelzigzag(node* root1){
int h=height(root1);
int flag=0;
for(int i=h;i>=1;i=i--){
if(flag==0){
printkthlevel(root1,i);
flag=1;
}
else{
printkthlevelreverse(root1,i);
flag=0;
}
}
return;
}
int main() {
node* root1=NULL;
root1=buildtree("true");
levelzigzag(root1);
return 0;
}
