#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
	int data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int val):left(nullptr),right(nullptr),data(val){};
};
bool isLeaf(TreeNode* root){
	return !root->right && !root->left;
}
void leftb(TreeNode* root,vector<int>&ans){
	TreeNode* curr=root->left;
	
	while(curr){
		if(!isLeaf(curr)){
			ans.push_back(curr->data);
		}
		
		if(curr->left){
		   curr= curr->left;
		}else{
			curr = curr->right;
		}
	}
}
void rightb(TreeNode* root,vector<int>&ans){
	TreeNode* curr=root->right;
	vector<int>temp;
	while(curr){
		if(!isLeaf(curr)){
			temp.push_back(curr->data);
		}
		
		if(curr->right){
		   curr= curr->left;
		}else{
			curr = curr->left;
		}
	}
	
	for(int i =temp.size()-1;i>=0;i--){
		ans.push_back(temp[i]);
	}
}

void addLeaves(TreeNode* root,vector<int>&ans){
	if(isLeaf(root))ans.push_back(root->data);
	if(root->left){
		addLeaves(root->left,ans);
	}
	if(root->right){
		addLeaves(root->right,ans);
	}
}

vector<int>bound(TreeNode*root){
	vector<int>ans;
	if(!root)return ans;
	
	if(!isLeaf(root))ans.push_back(root->data);
	
	leftb(root,ans);
	addLeaves(root,ans);
	rightb(root,ans);
	return ans;
}
TreeNode* buildTree(){
	int x;cin>>x;
	if(x == -1)return nullptr;
	TreeNode* root = new TreeNode(x);
 
	queue<TreeNode*>q;
	q.push(root);
 
	while(!q.empty()){
		auto u = q.front();
		q.pop();
 
		if(cin>>x && x!=-1){
			u->left=new TreeNode(x);
			q.push(u->left);
		}
 
			if(cin>>x && x!=-1){
			u->right=new TreeNode(x);
			q.push(u->right);
		}
	}
	return root;
}
int main() {
	TreeNode* root = buildTree();
    vector<int>ans = bound(root);
	for(auto&x : ans){
		cout<<x << " ";
	}
	return 0;
}