## Amazon Interview Question

Software Engineer / Developers**Country:**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