## Amazon Interview Question for Software Engineer / Developers

Team: SDE
Country: India
Interview Type: In-Person

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

whts the need of dp here??

1) push all the nodes on a stack as u traverse in an in order fashion

2) pop the top node assign its extra "next" pointer with NULL.

i.e last->next = null;

temp = last;

while((n = pop(theStack))
{
n->next = temp;
temp = n;
}

}

as simple as that!!..

whats DP doing here??

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

No need. Not all of the poster's hints are correct on all questions. In fact, you don't even need a stack.

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

I suppose the idea was to do this in a single traversal and without additional space to save the tree nodes. Though i agree that the above solution is easier.

alternatively it can be done as follows:

``````void fill_inorder_succ(node *t, node *remote_parent) {
if(t == 0)
return;
if(t->right != 0) {
t->next = leftmost_child(t->right);
find_inorder_suff(t->right, remote_parent);
} else
t->next = remote_parent;
fill_inorder_succ(t->left, t);
}
fill_inorder_succ(root, 0);``````

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

``````public binaryNode findSuccessor(binaryNode n)
{
if(n==root && n.right==null)
{
return null;
}
if(n.right!=null)
{
binaryNode temp=n.right;
while(temp.left!=null)
{
temp=temp.left;
}
return temp;
}
if(n==n.parent.right && n.right==null)
{
binaryNode temp=n.parent;
while(true)
{
if(temp==root)
{
System.out.println("This is the largest element, no successor exists");
return null;
}
if(temp==temp.parent.left)
{
return temp.parent;
}
else
{
temp=temp.parent;
}

}

}
if(n==n.parent.left && n.right==null)
{
return n.parent;
}
return null;
}

public void inOrderSuccessor(binaryNode b)
{
if(b==null)return;
inOrderSuccessor(b.left);
System.out.println("Values are "+b.data);
binaryNode a=findSuccessor(b);
if(a!=null)
{
System.out.println("Successor is "+a.data);
}
inOrderSuccessor(b.right);
}``````

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

in the above first inordesuccessor is called ..and then trivial...proper things are taken care

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

n.parent??
its a bst.. no parent ptr exists

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

``````public Tree inorder(Tree parent, Tree t) {
if (t ==  null) return null;

Tree last = inorder(parent, t.left);
if (last == null && parent != null) parent.next = t;
else last.next = t;

if (t.right == null) return t;
return inorder(t, t.right);
}``````

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

Using Iteration

1. if node 'n' has a rc, return min from the right subtree.
2. else, start from root and perform a traversal to find the node 'n', also store a candidate node, which is updated when you move to the left subtree.
3. when n is found(assuming that it exists in the tree), return candidate

Code

``````public node getInorderSuccessor(Node* n, Node* root)
{
if(n->right != null)
return findMin(n->right);

Node * y = root;
candidate = null;

while(y != n)
{
if(y->val > n->val)
{
y = y->left;
candidate = y;
}
else
{
y = y->right
}
}
return candidate;``````

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

Morris Algorithm should be the answer for this question.

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

M sure u kove this code...

void inorder_populate(node *p)
{ static node *temp=NULL;
if(p==NULL)
return;
else
{
inorder_populate(p->right);
p->next=temp;
temp=p;
inorder_populate(p->left);
}
}

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.