Amazon Interview Question
Software Engineer / DevelopersCountry: India
i=n-1;//global
struct node *construct(int post[],int in[],int n)
{
return const_post_in(post,in,0,n-1);
}
struct node * const_post_in(int post[],int in[],int s,int e)
{
int j;
if(s>e)
return NULL;
struct node *p=getnode();//allocate mem for node
p->info=post[i--];
for(j=s;in[j]!=post[i-1];j++)
;
p->r=const_post_in(post,in,j+1,e);
p->l=const_post_in(post,in,s,j-1);
return p;
}
Def buildTree(inorder[], postorder[])
{
j = len(postorder);
pre = postorder[j-1]; /* scan starting from the end of post order list */
for(i = j-2; i>=0; i--)
{
current = postorder[i];
curr_idx_in = find_position(current, inorder);
parent_idx_in = find_position(pre, inorder);
if (current_idx_in > parent_idx_in)
/* right child */
pre->right = current;
else if (current_idx_in < parent_idx_in)
pre->left = current;
pre = current;
}
}
Solution by Tushar Roy on geeksforgeeks:
Okie i got this approach..
suppose the example
inorder = A B C D E F G H I
postorder = A C E D B H I G F
This can b done recursively following way
you start reading postorder array from backwards. So take F , split inorder array into two subarray.
A B C D E and G H I
take G (before F in postorder) split GHI into null and H I, take I(before G in postorder) split into H I into H and null and so on.
following is the code which worked fine. Check it out.
typedef struct tree
{
int key;
struct tree * left;
struct tree * right;
}Tree;
Tree * createTreeFromPostorderInorder(int postorder[],
int inorder[],int left,int right, int pos)
{
if(left > right)
{
return NULL;
}
Tree *t = (Tree*)malloc(sizeof(Tree));
t->key = postorder[pos];
int index = search(inorder,left, right, t->key);
t->right = createTreeFromPostorderInorder(postorder,inorder,
index +1, right, pos -1);
t->left = createTreeFromPostorderInorder(postorder,inorder ,
left,index-1, pos - 1 - (right - index));
return t;
}
int search(int arr[],int left, int right,int key)
{
for(int i=left; i <= right; i++)
{
if( key == arr[i])
{
return i;
}
}
return -1;
}
int postorder[] = {'A', 'C' , 'E', 'D', 'B', 'H', 'I', 'G', 'F'};
int inorder[] = {'A', 'B','C','D','E','F','G','H','I'};
Tree *newTree = createTreeFromPostorderInorder(postorder,inorder,0,8,8);
If both Inorder and Postorder sequence are provided, then one possible implementation:
- Ran January 27, 2012