Data Structure Binary Tree: Inorder Tree Traversal without recursion and without stack!

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <stack>
 6 #include <string>
 7 #include <fstream>
 8 using namespace std;
 9 
10 struct node {
11     int data;
12     struct node *left, *right;
13     node() : data(0), left(NULL), right(NULL) { }
14     node(int d) : data(d), left(NULL), right(NULL) { }
15 };
16 
17 void print(node *root) {
18     if (!root) return;
19     node *cur = root;
20     while (cur) {
21         if (!cur->left) {
22             cout << cur->data << " ";
23             cur = cur->right;
24         }
25         else {
26             node *pre = cur->left;
27             while (pre->right && pre->right != cur) pre = pre->right;
28             if (pre->right == NULL) {
29                 pre->right = cur;
30                 cur = cur->left;
31             }
32             else {
33                 pre->right = NULL;
34                 cout << cur->data << " ";
35                 cur = cur->right;
36             }
37         }
38     }
39 }
40 
41 void prints(node *root) {
42     if (!root) return;
43     prints(root->left);
44     cout << root->data << " ";
45     prints(root->right);
46 }
47 
48 int main() {
49     node* root = new node(1);
50     root->left = new node(2);
51     root->right = new node(3);
52     root->left->left = new node(4);
53     root->left->right = new node(5);
54     print(root);
55     return 0;
56 }