#include <iostream>

 #include <vector>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <string>

 #include <fstream>

 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 print(node *root) {

     if (!root) return;

     node *cur = root;

     while (cur) {

         if (!cur->left) {

             cout << cur->data << " ";

             cur = cur->right;

         }

         else {

             node *pre = cur->left;

             while (pre->right && pre->right != cur) pre = pre->right;

             if (pre->right == NULL) {

                 pre->right = cur;

                 cur = cur->left;

             }

             else {

                 pre->right = NULL;

                 cout << cur->data << " ";

                 cur = cur->right;

             }

         }

     }

 }

 void prints(node *root) {

     if (!root) return;

     prints(root->left);

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

     prints(root->right);

 }

 int main() {

     node* root = new node();

     root->left = new node();

     root->right = new node();

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

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

     print(root);

     return ;

 }