Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
The question doesn't specify, but I'll assume that you receive a pointer to the root of the BST and a number whose predecessor wants to be found.
The idea is to try and search for the right-most child of the left branch of the node containing the given number (you'll have to search for that node first), if the node doesn't have a left branch, then you go up in the tree until you find the first parent node with smaller or equal value of the number. If no parent node meets that condition then there is no predecessor number which may happen iff the node containing the number is the left-most node of the tree.
Implementation is an iterative approach since recursive one needs to handle a few extra cases.
bool try_get_predecessor(TreeNode* root, int number, int& predecessor)
{
if (root == NULL)
return false;
stack<TreeNode*> previous;
TreeNode* current = root;
while (current != NULL)
{
if (current->value == number)
{
if (current->left == NULL)
{
if (previous.empty())
return false;
TreeNode* parent = previous.top();
while (!previous.empty() && parent->value > number)
{
previous.pop();
parent = previous.top();
}
if (parent->value > number)
return false;
return parent->value;
}
else
{
TreeNode* largest_pre = current->left;
TreeNode* next_pre = largest_pre;
while (next_pre != NULL)
{
largest_pre = next_pre;
next_pre = next_pre->right;
}
return largest_pre->value;
}
}
previous.push(current);
if (current->value > number)
current = current->left;
else
current = current->right;
}
return false;
}
typo:
Instead of
return parent->value;
It should be
predecessor = parent->value;
return false;
Case 1: Node is left most node of BST.
Return NULL
Case 2: Node has left sub tree.
In this case it is Maximum Node in the Left Sub-Tree. i.e., the right most node in the left sub-tree
would be the in-order predecessor.
Case 3: Node has no left sub-tree.
In this case in-order predecessor will be the node where we took the latest right turn.
C++ version:
NODE * find_predecessor(NODE * root, NODE * node)
{
NODE * temp = root, *parent = NULL;
if (node->left != NULL){ // Max of the Left Sub-Tree
temp = node->left;
while (temp->right != NULL)
temp = temp->right;
return temp;
}
while ( temp != node ){ // Find the Ancestor where we took latest Right Turn
if (node->data < temp->data){
temp = temp->left;
}
else {
parent = temp;
temp = temp->right;
}
}
return parent;
}
The idea is wherever we parse the right subtree while searching thats the in order predecessor. And whenever we parse the left subtree we have to remember for which parent we parsed the right subtree.
node = root
pre = NULL
found = False
while True:
if el < node.value:
node = node.left
continue
else if el > node.value:
pre = node
node = node.right
continue
else if node == NULL:
break
else:
found = True
break
if found == True:
if pre != NULL:
print pre
else:
print 'no predecessor exists'
else:
print 'element not found'
Time complexity: O(logn)
Space complexity: O(1)
Psuedocode for Predecessor of Tree
- Piyush March 23, 2014