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 node13,735 Views |
(45 votes, avg: 3.71)
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;
}
}
I think there´s a quicker and easier way to do this:
Just walk on the tree to find the nodes, when in a time you separate (spliting or going to different directions) to reach one or other node, in this time you find the lowest common ancestor:
struct node
{
int id;
node *left;
node *right;
}
ruleForWalk(int nodeid, int id){} /*here you put your rule to walk on the tree, usually the rule to order the tree is left:minor value and right:major
nodeid=the id of the node you are,
id=the id you´re searching,
return=-1 for left, 1 for right)*/
int walkInTheTree(int n1, int n2, node *root)
/*n1 and n2=the node ids*/
{
int e1;
int e2;
e1 = ruleForWalk(root->id,n1);
e2 = ruleForWalk(root->id,n2);
if(e1==e2) //if both go to the same way
{
if(e1==-1) return walkInTheTree(n1,n2,root->left);
else return walkInTheTree(n1,n2,root->right);
}
} else return root->id; //if the way splits
}
So just print the result of the walkInTheTree function. This algorythm is also O(logN).
gugamonte your ans is good but it would fail if node in question are adjacent nodes. In that case common ancestor will be one level up.
struct node
{
int id;
node *left;
node *right;
};
int commonAncestor(node* r, int id1, int 1d2)
{
int big, small;
small=(id1id2?id1:id2);
if(r == NULL )
return -1;
while(r!=NULL)
{
node* t =r;
if(smallid&&bigid)
r=r->left;
else if((small>r->id&&big>r->id)
r=r->right;
else if(smallid&&r->idid;
else if(smallid&&r->idid;
else
return -1;
}
}
you just have to traverse the binary tree until you find a node that is between id1 and id2 . thats it
My solution, considering all the IDs >= 0:
int lca(int id1, int id2, node n) {
int sx = (n.left != null) ? lca(id1, id2, n.left) : -1;
int dx = (n.right != null) ? lca(id1, id2, n.right) : -1;
int lca = -1;
if (sx != -1 and dx == -1) lca = (n.id != id1 and n.id != id2) ? sx : n.id;
if (sx == -1 and dx != -1) lca = (n.id != id1 and n.id != id2) ? dx : n.id;
if (sx != -1 and dx != -1) lca = n.id;
if (sx == -1 and dx == -1) lca = (n.id != id1 and n.id != id2) ? -1 : n.id;
return lca;
}
Bye.
I would just traverse the tree twice , each time storing the id of each node’s ancestor until i reach the intended node.
Say this becomes array1 and has 10 elements
Similarly array2 has 15 elements
for(i = 9 ; i >= 0 ; i–)
{
if(array1[i] == array2[i])
return array1[i];
}
This should give the most recent common ancestor.
If i becomes zero then its the root which is the common ancestor.
Leave an Answer/Comment