Amazon Interview Question
Country: United States
if you will write few lines on algo and approach as well it would be easy and quick to understand logic.
nice solution by the way...
Of course it will come out of the while loop. In every iteration, currNode moves down one level in the tree no matter which condition is met. So eventually it will hit a leave node. Then it will exit.
Consider a case when the target node is somewhere in between the tree, I mean to say target node has more than one node in left and right.
1) So according to your code when (currNode.val == target.val)
the value of current node is set to currNode.right (which is desired output). Now consider there are still few nodes in right.
So now again the while condition is checked and it is true hence it will enter in while block.
2) It will go in
else if (currNode.val > target.val) {
candidate = currNode;
currNode = currNode.left;
}
block and currNode is again set to currNode.left
again it will check the while condition which is still true and step 1 will be repeated.
I hope you are getting what i mean to say..
Correct me if I am wrong.
Thanks #chriscow
Consider target is 5 and the tree is
5
/ \
1 10
/ \
6 11
currNode = root to start with. Now let me walk through the iteration for you:
1. currNode = 5 == target, so currNode = currNode.right = 10.
2. currNode = 10 > target = 5, so candidate = 10 and currNode = currNode.left = 6.
3. currNode = 6 > target = 5, so candidate = 6 and currNode = currNode.left = null.
4. currNode = null. Exit while loop.
Please make sure you understand what is a BST.
1.We can traverse tree in inorder manner.
2. We will have two pointers prev and current.
3.When prev is equal to the node given current pointer will b our answer.
Correct me If I m wrong.
directly walk thru the whole BST is not ideal.
One possible solution is this -
1. you check the given target node, and see if the node has a right child, if it has the successor is the most left element in the right child tree (let me know if you can't understand this part.)
2. if the given target node doesn't have a right child, means you need to figure out the element that is just bigger than the target, because the target has no right child, it can tell that by itself, so what to do next is to utilize and walk thru the BST , keep a track of the most recent element that is bigger than the target element until we find the element.
Return Null if such element doesn't exist.
Node FindInOrderSuccessorBST(node root, node targetNode)
{
If (targetNode == null || root == null) return null;
// if the target has a right child. The successor is the most left child in right child tree.
If (targetNode.Right != null)
{
Return FindMostLeftNode(targetNode.Right);
}
// if the target has no right child. We do a search for the target Node in the BST and keep tracking for the last found element that is bigger than the target element, if such element exists it is the successor of the target , otherwise return null.
Return GetLastBiggerElement(root,targetNode);
}
Node GetLastBiggerElement(node root, node targetNode)
{
If (root != null) {
If (root.value > targetNode.value)
{
Return root.Left == null ? Root : GetlastBiggerElement(root.Left,targetNode) ?? Root;
}
If (root .value < targetNode.value)
{
Get:LastBiggerElement(Root.Right) ;
}
}
Return null; // root is null or we found the element.
}
Node FindMostLeftNode (node Root)
{
If (root == null) return null;
Return Root.Left != null FindMostLeftNode(Root.Left) : Root;
}
find a node with a given value, keeping track of parent too
y=0;
x=root;
z = 0;
while( x != 0 && x->value != value )
{
y = x;
if( x -> value < value )
x = x->right; // value is in right subtree of x
else
{
z = x;
x = x->left; // value is in left subtree of x
}
}
Now having x and y with x pointing to given value and y pointing to parent.
Inorder successor will be smallest in right subtree of x. If x has no right subtree then if x is either left child of y , in which case y is next highest value after x. If x is however a right child, then return to root and start finding x->data again, wherever you took left turn last is successor, thats z
if( x->right != 0 )
return minimum(x->right);
if(x == y->left )
return y;
return z;
NODE * inorder_successor(NODE *p, NODE *nodeToBeSearched)
{
static bool found =0;
if (p == NULL)
return NULL;
else
{
if (p == nodeToBeSearched) {
return p;
}
else
{
NODE *nodefound = inorder_successor(p->left, nodeToBeSearched);
if (nodefound != NULL) {
if (!found) {
found = 1;
return p;
}
else
return nodefound;
}
else
{
return inorder_successor(p->right, nodeToBeSearched);
}
}
}
}
A basic inorder traversal can solve the problem as other posters have pointed out. But it is wasteful. In the case the target is in the right subtree of the root, traversing the whole left subtree is useless.
In fact, a modified binary search is more suitable here. Notice that
Finding the first entry larger than target in a sorted array is a simple variation of binary search in a sorted array. Here we can use a similar idea for binary search in BST.
During the binary search in BST, there are two cases:
1. if currNode <= target, the successor must be in the right subtree. Continue the binary search in the right subtree.
2. if currNode > target, two possibilities here: successor is also in the left subtree, or currNode is the successor if target is the largest in the subtree. Memorize currNode as the candidate for successor. It will be overwritten if target is in the left subtree of some other node further down.
When return, pay attention to the two corner cases when the successor doesn't not exist:
1. target cannot be found in the tree;
2. target is the largest in the tree, so it has no inorder successor.
Here is my Java implementation.
- chriscow January 24, 2014