Construct binary tree from inorder and postorder traversal

Given post-order and in-order traversal of a tree, construct the binary tree.

C++:
01 bool checkRange(int start, int end, int a)
02 {
03     return ((a>=start)&&(a<=end));
04 }
05 
06 int findIndex(int *A, int start, int end, int k)
07 {
08     for(int i=start;i<=end;i++){
09         if(A[i]==k)
10             return i;
11     }
12     return 1;
13 }
14 
15 Node* buildTree(int* P, int* I, int size, int p_start, int p_end, int i_start, int i_end)
16 {
17     if(!checkRange(0,size1,p_start)||!checkRange(0,size1,p_end))
18         return NULL;
19     if(!checkRange(0,size1,i_start)||!checkRange(0,size1,i_end))
20         return NULL;
21     if((p_start>p_end)||(i_start>i_end))
22         return NULL;
23     int s=P[p_end];
24     int m=findIndex(I,i_start,i_end,s);
25     if(!checkRange(i_start,i_end,m))
26         return NULL;
27     Node* head=new Node;
28     head->value=s;
29     head->left=buildTree(P,I,size,p_start,p_start+mi_start1,i_start,m1);
30     head->right=buildTree(P,I,size,p_start+mi_start,p_end1,m+1,i_end);
31     return head;
32 }
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s