#include <iostream>

 #include <vector>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <string>

 #include <fstream>

 #include <map>

 using namespace std;

 struct node {

     int data;

     struct node *left, *right;

     node() : data(), left(NULL), right(NULL) { }

     node(int d) : data(d), left(NULL), right(NULL) { }

 };

 void prints(node *root) {

     if (!root) return;

     stack<node*> S;

     do {

         while (root) {

             if (root->right) S.push(root->right);

             S.push(root);

             root = root->left;

         }

         root = S.top();

         S.pop();

         if (root->right && !S.empty() && root->right == S.top()) {

             S.pop();

             S.push(root);

             root = root->right;

         }

         else {

             cout << root->data << " ";

             root = NULL;

         }

     } while (!S.empty());

 }

 int main() {

     node *root = new node();

     root->left = new node();

     root->right = new node();

     root->left->left = new node();

     root->left->right = new node();

     root->right->left = new node();

     root->right->right = new node();

     prints(root);

     return ;

 }