1. /*Program name: Create full binary tree using its inorder and preorder
2. traversal*/
3.  
4. #include<iostream.h>
5. #include<conio.h>
6.  
7. struct node{
8. struct node* left;
9. struct node* right;
10. int data;
11. };
12.  
13. struct node* root;
14. //6 buildtree execution start
15. void buildtree(struct node *b, int left_selected ,int* preorder, int* inorder)
16. {
17.       int preorder_1[8] = {-1,-1,-1,-1,-1,-1,-1,-1};//7.initialize preorder_1
18.       int preorder_2[8] = {-1,-1,-1,-1,-1,-1,-1,-1};//8.initialize preorder_2
19.  
20.       int inorder_1[8] = {-1,-1,-1,-1,-1,-1,-1,-1}; //9.initialize inorder_1;
21.       int inorder_2[8] = {-1,-1,-1,-1,-1,-1,-1,-1}; //10.initilaize inorder_2
22.  
23.       int i, j, k1, k2;
24.  
25.  
26.  
27.       //11.creation of root node of the tree
28.  
29.       if(b==NULL)
30.       {
31.             root = b = new node;
32.             b->data = preorder[0];    //12. root node is preorder first element
33.             b->left = b->right = NULL; //13. root left and right is Null;
34.       }
35.       else
36.       {
37.             node* tmp = new node;
38.             tmp->data = preorder[0];
39.             tmp->left = tmp->right = NULL;
40.  
41.             if(left_selected)
42.                   b->left = tmp;
43.             else
44.                   b->right = tmp;
45.  
46.             b = tmp;
47.       }
48.  
49. i = 0;  //14. i=0;
50.  
51. while(inorder[i] != preorder[0])  //15.this logic will store inorder left element with respect to preoeder node.                                  // in inorder traversal  and store it in Inorder_1.
52. {
53.       inorder_1[i] = inorder[i];
54.       i++;
55. }
56.  
57. i++;  //17 indicate the current preorder node position in inorder list
58. j = 0;
59.  
60. while(inorder[i] != -1 ) //18 this logic will store inorder right element with respect to preoeder node.
61. {
62.       inorder_2[j] = inorder[i];
63.       j++;
64.       i++;
65. }
66.  
67. i = j = k1 = k2 = 0;
68.  
69. while(preorder[i] != -1 ) //19.
70. {
71.       i++;
72.       int flag = 0;
73.       j = 0;
74.       while(inorder_1[j] != -1 )
75.       {
76.             if (inorder_1[j] == preorder[i])
77.             {
78.                   flag = 1;
79.                   break;
80.             }
81.       j++;
82.  
83.       }
84.  
85.       if(flag)
86.       {
87.             preorder_1[k1] = preorder[i];
88.             k1++;
89.       }
90.       else
91.       {
92.             preorder_2[k2] = preorder[i];
93.             k2++;
94.       }
95.  
96. }
97.  
98. if(preorder_1[0] != -1)
99.       buildtree(b, 1, preorder_1, inorder_1);
100.  
101. if(preorder_2[0] != -1)
102.       buildtree(b, 0, preorder_2, inorder_2);
103.  
104.  
105. }
106.  
107. void preorder_traversal()
108. {
109.       int top=-1;
110.       struct node*stack[40],*trav;
111.  
112.       trav=root;
113.  
114.       while(1)
115.       {
116.             while(trav!=NULL)
117.             {
118.                   cout<<" "<<trav->data;
119.                   top++;
120.                   stack[top]=trav;
121.                   trav=trav->left;
122.             }
123.             while(top!=-1)
124.             {
125.                   trav=stack[top];
126.                   top--;
127.                   trav=trav->right;
128.  
129.                   while(trav!=NULL)
130.                   {
131.                         cout<<" "<<trav->data;
132.                         top++;
133.                         stack[top]=trav;
134.                         trav=trav->left;
135.                   }
136.             }
137.             if(top==-1)
138.             {
139.                   break;
140.             }
141.       }
142. }
143.  
144.  
145. int main()
146. {
147.       clrscr();
148.       root = NULL; //1. initialize root by null
149.       int preorder[] = {7,10,4,3,1,2,8,11,-1}; //2. preorder is given
150.       int inorder[] = {4,10,3,1,7,11,8,2,-1}; //3.inorder is given
151.       buildtree(root, 1 ,preorder, inorder);//4. buildtree is a function
152.  
153.       cout<<"\nResultant Tree is (preorder):"; //.it will print msg.
154.       preorder_traversal(); //. call preorder traversal
155.        getch();
156.       return 1;
157.       //getch();
158. }