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

struct TreeNode{
	TreeNode* left;
	TreeNode* right;
	
	int data;
	TreeNode(int val):left(nullptr),right(nullptr),data(val){};
};

vector<int>preT(TreeNode* root){
	vector<int>pre;
		if(root == nullptr)
        return pre;
	stack<TreeNode*>st;
	
	st.push(root);

	while(!st.empty()){
		auto node = st.top();st.pop();
		
		pre.push_back(node->data);
		
	    if(node->right){
	    	st.push(node->right);
	    }
	    
	    if(node->left){
	    	st.push(node->left);
	    }
	}
	
return pre;	
}

TreeNode* buildTree(){
	int x;
	cin>>x;
	if(x==-1)return nullptr;
	TreeNode* root = new TreeNode(x);
	queue<TreeNode*>st;
	st.push(root);
	
	while(!st.empty()){
		auto node = st.front();st.pop();
		
		
		if(cin>>x && x != -1){
			node->left = new TreeNode(x);
			st.push(node->left);
		}
		
	
		if(cin>>x && x != -1){
			node->right = new TreeNode(x);
			st.push(node->right);
		}
	}
	return root;
}

int main() {
    TreeNode* root = buildTree();
    vector<int>pre = preT(root);
    for(int x:pre)cout<< x <<" ";
	return 0;
}