Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle
Country: India
Interview Type: In-Person
aren't you being funny rick...if searching for something in a binary search tree is taking more than O(h) time then you are definitely doing something wrong.
Artist, what I meant was that, it is straightforward to first search the given element and then seek for its successor. The method given above is definitely much better, and I have no clue how did Duke87 come up with it. That's why I ask.
hmm...look at my comment below on CodePredator's solution. Searching for the number and finding the next successor was out of question as you don't know whether the number is present in the tree or not...
Duke87,
Your algorithm is conceptually correct, but for the sake of completeness you might like to consider addressing the below case which currently will return wrong answer.
Consider a tree with single node whose value is INT_MIN. In this case we expect a null value or something similar to be returned to indicate that the tree does not have any solution but your solution will return INT_MIN which is the value of the root node and is incorrect answer.
if tree is created in this order 13 6 9 10 11
if number is 9 we get answer 11 and not 10
AK:
Building a BST by adding 13, followed by 6, followed by 9,..finally by adding 11, we'll have a tree whose root =13. Root=13 will have only left child=6. 6 will have 9 as right child, 9 in turn will have 10 as right child and finally 10 will have 11 as right child.
With this BST, if you apply 'Duke87''s algorithm, then the value of nextBig
after 1st iteration is : 13 (since 13 > 9 )
after 2nd iteration is : 13 (i.e. unchanged since 6 < 9 )
after 3rd iteration is : 13 (i.e. unchanged since 9 > 9 is false)
after 4th iteration is : 10 (since 10 > 9 )
Thus final answer is 10 (not 11).
Let us know how did you get 11.
To : buckCherry's reply on November 06, 2012
Well I believe it should always be part of question on what should function return if no “next big number” found. If not mentioned by interviewer then interviewee should really ask.
If function returns an integer value then there is no question of null. It purely depends on what client code expects and how intelligent client code is. If client is intelligent enough to determine that returned value is equal or less than input number then client code can understand that there isn’t exist next big number in the tree. This is one of the scenario and solution I could think of. But again it depends on what client code really expects, in short what is the exact requirement.
And yes, in terms of finding the next big number code works fine.
@maverick:
Not sure what you intend to tell towards my post. Anyway let me first quote this excerpts from my post "..we expect a null value or something similar to be returned to indicate that the tree does not have any solution..".
So clearly null was just an option and I think you've missed out the "something similar" part of my post. Let me know if you still have any confusion!!
Yes I understood and agreed what you meant to say. I just wanted to clarify because you reply is very specific to this solution code which returns int.
I was just trying to find out what could be that “something similar” and tried to explain on that a bit.
It’s great to have concrete answer of question raised on a concrete solution ,not just conceptual answer.
@mathan: the answer to your problem is trivial...you'll have to go through all the nodes, checking if the value at a given node is less than the previously found max and more than the given number, then update the max.
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
node *left;
int data;
node *right;
};
node *insert(node *root, int data);
void findnextbigger(node *root, int data);
int main()
{
node *root = NULL;
int n1 =0;
int n,i;
int input[20];
printf("\n enter size of array=");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&input[i]);
printf("\n Enter the node data for which next bigger data to find:");
scanf("%d",&n1);
for(i=0;i<n;i++)
{
root = insert(root, input[i]);
}
findnextbigger(root, n1);
return 0;
}
#define INT_MIN -999
void findnextbigger(node *root, int n1)
{
node *ptr = root;
node *tmp= NULL;
int nextbigdata = INT_MIN;
while(ptr !=NULL)
{
if(ptr->data == n1)
{
/*find inorder successor of n1*/
printf("\n find inorder successor of n1");
tmp = ptr->right;
if(tmp != NULL)
{
while(tmp->left != NULL) tmp = tmp->left;
printf("\nNext Bigger node value of %d is %d: ",n1,tmp->data);
break;
}
else
{
if(nextbigdata == INT_MIN)
{
/* last node */
printf("\n No Next Bigger value than %d", n1);
}
else
{
printf("\nNext Bigger node value of %d is %d: ",n1,nextbigdata);
}
break;
}
}
else if(n1 < ptr->data)
{
nextbigdata = ptr->data;
ptr = ptr->left;
}
else if(n1 > ptr->data)
{
ptr = ptr->right;
}
}
}
node *insert(node *root, int data)
{
if(root == NULL)
{
root = (node *)malloc(sizeof(node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
if(root->data > data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
you should add a condition that is
if (nextBig ==INT_MIN )
no number is present in the BST which is greater than given number.
Just for better understanding.
1. Search for the number ( TC: O(h) )
2. Find its in order successor ( TC: O(h) )
Total TC: O(h) but in two passes
int nextInBST(int num, Node root)
{
if(root == NULL)
return -999;
int n;
n = nextIntBST(int num, Node root->left);
if(n != -999)
return n;
if(root->info > num)
return root->info;
n = nextIntBST(int num, Node root->right);
return n;
}
int nextIntBST(int num, node* root)
{
if(root == NULL)
return -999;
int n;
n = nextIntBST(num, root->left);
if(n != -999)
return n;
if(root->data > num)
return root->data;
n = nextIntBST( num, root->right);
return n;
}
It is a nice solution, the idea is the first successor that is greater than the number in "In order traversal"
Nice but not the best. The worst case time taken for this algorithm will be O(n) (when there is no element bigger than the given number or the biggest number in the tree is the answer) which makes it a O(n) algorithm. Now if searching for anything in a binary search tree is taking more than O(h) time than you should really think twice. In the above algorithm you are blindly attacking the root->left which is not required if root->data was less than the given number. In that case you already know that the number you are searching for lies, if present, in the right sub tree of the root element
also rather than returning -999 you might want to return something that you will be sure of is not a solution (say for example n-1) what if the solution itself is -999?
We can do it in O(h) complexity by using the following method:
1. Search for the element 'n' in the BST, as you search add the elements in the path to a stack
2. If element is found and the element has a right subtree, the leftmost element in the right subtree will be the next biggest element.
3. If element is not found or the element is found but does not have right subtree, then pop elements from the stack until you find an element that is greater than 'n'. This will be the next biggest element.
Funda : by maintaining a stack we can traverse back and easily find the inorder successor with in O(h) time.
If you are taking extra space ( a stack ) then you don't have to perform complex algorithm, just storing in order traversal in an array would do it!
Do an inorder traversal of the BST. In place of print test whether node->data-number is negative. If yes print that number.Complexity O(n)
static bool is_found = 0;
void closest_num( node* root, int number )
{
if( root == NULL)
return;
closest_num(root->left, number);
if( !is_found &&root->data > num ){
cout << root->data;
is_found = 1;
}
closest_num(root->right, number);
}
int search_num( node *root, int num)
{
if(NULL == root)
return 0;
if(num == root->data)
return 1;
if(num > root->data && root->right)
{
// recursive call with right node
return(search_num(root->right, num))
}
else if(num < root->data && root->left)
{
// recursive call with left node
return(search_num(root->left, num))
}
return 0
}
search number recursively,
when found
check if it has right child .
if yes , this is the number
if no right child
return
now the calls will start unwinding check number with data of root
if big this is the number.
def inOrderSuccessorMain(root, node):
if root == None or node==None or (root.left==None and root.right):
return False
return inOrderSuccessorHelper(root, node)
def inOrderSuccessorHelper(root, node):
found = False
if root == None:#node not found then return False
return found
elif node.data < root.data:#node less than root then search left subtree
found = inOrderSuccessor(root.left, node).
if found == None:#if found=None then root is the successor
return root
elif node.data > root.data:#node less than root then search right subtree
found = inOrderSuccessor(root.right, node)#found can be False, None, or some node
else:
if root.right != None:# Find left most node of right subtree
found = rightSubTree(root.right)
else
return None # return None if no right node exists
return found
def rightSubTree(root):
if root.left == None:
return root
else:
return rightSubTree(root.left)
Traverse the BST in order and keep track of the previous value. Since BST inorder traversal results in ascending order, if the previous node visited is the required number, then the current node is the next big number. Below is the pseudo code.
Node* prevNode;
Search(Node* node,int n)
{
if(node== NULL)
return;
Search(node->left,n);
if(prevNode->data == n)
Print(node->data);
prevNode= node;
Search(node->right,n)
Traverse the tree inOrder, & set prev (when node with data 'num' found).
If prev is already found, then return curr (i.e.- root) in recursion.
Handles all cases. Returns NULL if succ/num node doesn't exist
struct node * inOrderSuccessor(struct node * root, int num){
struct node * prev = NULL;
return find(root, prev, num);
}
struct node * find(struct node * root, struct node *& prev, int num){
static bool found = false;
static struct node * succ = NULL;
if(root){
find(root->left, prev, num);
if(prev && !found){
found = true;
succ = root;
}
else if(root->data == num){
prev = root;
}
if(!found)
find(root->right, prev, num);
}
return succ;
}
Break the problem into two steps: a) find its number b) find its successor.
To find a number in a BST, you look at the root value. If you have match, you're done. If your desired value is less than root, search the left subtree; otherwise, search the right subtree.
To find the successor of a BST's root note, find the minimum value of the right subtree.
To find the minimum value of a tree, determine if the root node has a left subtree. If it does, recursively return the minimum value of the left subtree. Otherwise, return the root's value.
this code will work for both case if n is present in BST and if n is not a part of BST
- Duke87 November 05, 2012int nextBigNum( struct node * root, int n)
{
int nextBig =INT_MIN;
struct node * temp =root;
while(root!=NULL)
{
if(root->data > n)
{
nextBig=root->data;
root=root->left;
}
else
{
root=root->right;
}
}
return nextBig;
}