## Amazon Interview Question

Country: United States

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

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

``successor = the smallest node larger than target``

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.

``````public class inorderSuccessor {
public static TreeNode iterativeSolution(TreeNode root, TreeNode target) {
if (root == null || target == null) return null;
boolean targetFound = false;
TreeNode currNode = root, candidate=null;
while (currNode != null) {
if (currNode.val == target.val) {
targetFound = true;
currNode = currNode.right;
}
else if (currNode.val > target.val) {
candidate = currNode;
currNode = currNode.left;
}
else {// currNode.val < target.val
currNode = currNode.right;
}
}
return targetFound ? candidate : null;
}
}``````

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

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...

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

Thanks for the suggestion @PKT. Brief explanation added.

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

I wonder whether it will ever come out of while loop or not....!!!

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

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.

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

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

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

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.

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

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.

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

You are not utilizing the fact that it is a BST. Your solution takes O(n) while it could be done in O(logn).

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

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

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

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

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

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

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

This is not correct.
Consider the case for a single node bst and nodeToBeSearched is the root. You will be returning nodeToBeSearched itself, while the correct output should be NULL since there is no successor for it.

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.