Amazon Interview Question
Software Engineer / Developers//pseudo-code, given an input param of X :
1. Start traversing thru the tree
2. Chk. if X=< 0, if not return 0
3. Chk. if X < Parent, if not return 0
4. Chk. if Node has children, if not return 0
5.1. Chk. If Node.right < X => return predecessor
5.2. Chk. If Node.left < X => return predecessor
6. //fall thru if neither 5.1 || 5.2 ,
Continue at step 4. and loop until done
first find the node with value x
then just find the inorder successor of that node :)
code :
int nextgreater(int x,struct node *r)
{
struct node *temp=r;
if(!r)
{
printf("not exist");
return -1;
}
while(temp!=NULL)
{
if(temp->value==x)
break;
if(x>temp->value)
temp=temp->right;
else
temp=temp->left;}
if(temp==NULL)
{
printf("NOT exist");
return -1;
}
if(temp->right)
{
temp=temp->right;
while(temp->left)
temp=temp->left;}
}
else
{
temp=r;
succ=NULL;
while(temp)
{
if(temp->value>x)
{
succ=temp;
temp=temp->left;
}
if(temp->value==x)
break;
if(temp-value<x)
{
temp=temp->right;
}
}
return succ;
}
return temp;
}
I think the 2nd post provides best answer for the
most general case. The problem definition does not
specify that the BST contains a value = X. Furthermore
it is not given what the structure of the tree is, I.e. number of child nodes (left,right). Also one has to
validate x for any possible values, nulls & 0.
In Ruby:
# Given a binary search tree and a value X, find the node with value
# immediately greater than X.
class Node
attr_accessor :value, :left, :right
def initialize(value=nil, left=nil, right=nil)
@value = value
@left = left
@right = right
end
end
def find_minimum(root_node)
return root_node if root_node.left == nil
find_minimum(root_node.left)
end
def find_pesky_sibling(root_node, value, parents=[])
# If we can't find the value, return nil
if root_node == nil
return nil
elsif value == root_node.value
# If we don't have a right node, return the greater parent
if root_node.right == nil
parents.each do |parent|
if parent.value > value
return parent
end
end
return nil
# Otherwise, return the minimum value in the right sub-tree
else
return find_minimum(root_node.right)
end
# If our value is less than the current node, check the left sub-tree
elsif value < root_node.value
find_pesky_sibling(root_node.left, value, parents << root_node)
# If our value is more than the current node, check the right sub-tree
else
find_pesky_sibling(root_node.right, value, parents << root_node)
end
end
# Build example binary tree
# 10
# / \
# 7 15
# / \ / \
# 4 9 11 20
# /
# 8
n8 = Node.new(8)
n9 = Node.new(9, n8, nil)
n4 = Node.new(4)
n7 = Node.new(7, n4, n9)
n20 = Node.new(20)
n11 = Node.new(11)
n15 = Node.new(15, n11, n20)
root_node = n10 = Node.new(10, n7, n15)
# Find solution
puts find_pesky_sibling(root_node, 9).inspect
return inorder successor of node with value X
- Anonymous July 21, 2011