Amazon Interview Question
Software Engineer / DevelopersTeam: 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??