Data Structure Binary Tree: Connect nodes at same level using constant extra space

http://www.geeksforgeeks.org/connect-nodes-at-same-level-with-o1-extra-space/

recursive:

 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, *next;
13     node() : data(0), left(NULL), right(NULL), next(NULL) { }
14     node(int d) : data(d), left(NULL), right(NULL), next(NULL) { }
15 };
16 
17 node *getnext(node *root) {
18     node *next = root->next;
19     while (next) {
20         if (next->left) return next->left;
21         if (next->right) return next->right;
22         next = next->next;
23     }
24     return NULL;
25 }
26 
27 void _connect(node *root) {
28     if (!root) return;
29     if (root->next) _connect(root->next);
30     if (root->left) {
31         if (root->right) {
32             root->left->next = root->right;
33             root->right->next = getnext(root);
34         }
35         else root->left->next = getnext(root);
36         _connect(root->left);
37     }
38     else if (root->right) {
39         root->right->next = getnext(root);
40         _connect(root->right);
41     }
42     else _connect(root->next);
43 }
44 
45 void connect(node *root) {
46     if (!root) return;
47     root->next = NULL;
48     _connect(root);
49 }
50 
51 int main() {
52     node *root = new node(10);
53     root->left = new node(8);
54     root->right = new node(2);
55     root->left->left = new node(3);
56     root->right->right = new node(90);
57     connect(root);
58     cout << root->data << "->" << (root->next? root->next->data : -1) << endl;
59     cout << root->left->data << "->" << (root->left->next? root->left->next->data : -1) << endl;
60     cout << root->right->data << "->" << (root->right->next? root->right->next->data : -1) << endl;
61     cout << root->left->left->data << "->" << (root->left->left->next? root->left->left->next->data : -1) << endl;
62     cout << root->right->right->data << "->" << (root->right->right->next? root->right->right->next->data : -1) << endl;
63     return 0;
64 }

iterative(better)

 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, *next;
13     node() : data(0), left(NULL), right(NULL), next(NULL) { }
14     node(int d) : data(d), left(NULL), right(NULL), next(NULL) { }
15 };
16 
17 node *getnext(node *root) {
18     node *next = root->next;
19     while (next) {
20         if (next->left) return next->left;
21         if (next->right) return next->right;
22         next = next->next;
23     }
24     return NULL;
25 }
26 
27 void connect(node *root) {
28     if (!root) return;
29     root->next = NULL;
30     while (root) {
31         node *p = root;
32         while (p) {
33             if (p->left) {
34                 if (p->right) p->left->next = p->right;
35                 else p->left->next = getnext(p);
36             }
37             if (p->right) p->right->next = getnext(p);
38             p = p->next;
39         }
40         if (root->left) root = root->left;
41         else if (root->right) root = root->right;
42         else root = root->next;
43     }
44 }
45 
46 int main() {
47     node *root = new node(10);
48     root->left = new node(8);
49     root->right = new node(2);
50     root->left->left = new node(3);
51     root->right->right = new node(90);
52     connect(root);
53     cout << root->data << "->" << (root->next? root->next->data : -1) << endl;
54     cout << root->left->data << "->" << (root->left->next? root->left->next->data : -1) << endl;
55     cout << root->right->data << "->" << (root->right->next? root->right->next->data : -1) << endl;
56     cout << root->left->left->data << "->" << (root->left->left->next? root->left->left->next->data : -1) << endl;
57     cout << root->right->right->data << "->" << (root->right->right->next? root->right->right->next->data : -1) << endl;
58     return 0;
59 }