Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
O(lgn)
NodePtr temp = t;
if(!search(t, a) || !search(t, b)) //Existence
return 0;
while(temp != 0)
{
if(a < temp->ele && b > temp->ele || a > temp->ele && b < temp->ele)
return temp;
else if(a == temp->ele)
return temp;
else if(b == temp->ele)
return temp;
else if(a < temp-> ele && b < temp->ele)
temp = temp->left;
else
temp = temp->right;
}
return temp;
Beautifully coded answer at the below link :
- Anonymous March 25, 2012stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree