## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

If both Inorder and Postorder sequence are provided, then one possible implementation:

``````int j= inorder.Count -1;

TreeNode ConstructNodes(List<Node> inorder, List<Node> postOrder)
{
int index = -1;
TreeNode n = new TreeNode();
n.Data = postOrder[j].Data;

//gets the index of the "postOrder[j].data" element in the inorder list.
index = getIndex(inorder, postOrder[j].Data);
inorder[index].Processed = true;

if ((index < inorder.Count -1) && (!inorder[index + 1].Processed))
{
j--;
n.Right = ConstructNodes(inorder, postOrder);
}
else
n.Right = null;

if ((index > 0) && (!inorder[index -1].Processed))
{
j--;
n.Left = ConstructNodes(inorder, postOrder);
}
else
n.Left = null;

return n;
}``````

Comment hidden because of low score. Click to expand.
0

Did the interviewer or the question assume that all the data elements in post and inorder traversals are unique ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

We will also need inorder traversal of the tree to completely produce the tree.

Comment hidden because of low score. Click to expand.
0

Wont you also need whether each node is a leaf or non-leaf?

Comment hidden because of low score. Click to expand.
0

no need. Just postorder and inorder sequence is enough to build back the tree

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````FI(k, lo, hi)
for each i from lo to hi
if(in[i] == k)
break
return i

CT(lo, hi, mn, mx)
n = CN(p[mn])
p = FI(p[lo], lo, hi)
d1 = p - lo
d2 = hi- p
n->l = CT(lo, p-1, mn+1, mn +1+d1-1)
n->r = CT(p+1, hi, mn+d1+1, mx)
return n``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.