Data Structure Binary Tree: Convert a given Binary Tree to Doubly Linked List

http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/

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

http://www.geeksforgeeks.org/convert-a-given-binary-tree-to-doubly-linked-list-set-2/

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

http://www.geeksforgeeks.org/convert-given-binary-tree-doubly-linked-list-set-3/

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