## Amazon Interview Question

Software Engineer / Developers**Team:**SDE

**Country:**India

**Interview Type:**In-Person

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

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

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

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

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

whts the need of dp here??

- Duh!! February 03, 20121) 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??