Interview Questions And Answers 
-
Here’s one I was asked during my interview:
- binary tree, nodes, each node has an ID
- root node of the tree
structure node
{
int id;
node *
left;node *
right;}
- problem: given node id 1, and node id 2, determine the
lowest common ancestor of these 2 nodes- input:
id1, id2, root- out: node
id of this ancestor node1,244 Views |
(7 votes, avg: 3.57)
Loading ...
Answers »
Our Sponsors
Our Sponsors
struct node
{
node(int i, node * l =NULL, node * r=NULL): id(i), left(l), right(r) {};
int id;
node * left;
node * right;
};
bool FindNode(node * root, int id, std::vector& vec)
{
if (root == NULL)
return false;
else if(root->id == id)
{
vec.push_back(id);
return true;
}
else if ( FindNode( root->left, id, vec))
{
vec.push_back(root->id);
return true;
}
else if ( FindNode(root->right, id, vec))
{
vec.push_back(root->id);
return true;
}
else
return false;
};
bool FindCommonAncestor( node * root, int n1, int n2, int & anc)
{
std::vector v1, v2;
if (FindNode(root, n1, v1) && FindNode(root, n2, v2))
{
//has common;
int anc;
while (!v1.empty() && !v2.empty())
{
int a1 = v1.back();
int a2 = v2.back();
if ( a1 == a2)
anc = a1;
v1.pop_back();
v2.pop_back();
}
return true;
}
else
return false;
}
Hi, sorry for my English, I’m from Russia. My first solution was the same. But then, I wondered if tree is ordered by Id. Then algorithm could be more optimal. And your algorithm has complexity O(2N), I think one tree traversal (O(N) is enough.
Here is a better one:
struct node
{
node(int i, node * l =NULL, node * r=NULL): id(i), left(l), right(r) {};
int id;
node * left;
node * right;
};
enum res { none = 0, first, second, both };
res FindCommonRoot( node * root, int d1, int d2, int &anc, bool & find )
{
if (root == NULL)
return none;
else
{
res ret = none;
if (root->id == d1 )
ret = first;
if (root->id == d2)
ret = second;
res r1= FindCommonRoot(root->left, d1, d2, anc, find);
res r2 = FindCommonRoot(root->right, d1, d2, anc, find);
ret = (res) (r1 | r2 | ret);
if (ret == both )
{
anc = root->id;
find = true;
return none;
}
return ret;
}
}
Leave an Answer/Comment