Microsoft Interview Question
Development Support Engineersbool findNode(Node root, Node node){
if(root==null)
reutrn False;
elseif(root==node)
return True;
elseif(findNode(root.left,node)||findNode(root.right,node))
return True;
else
return False
}
how does this find the least common parent. you are finding the path from the root node.
first find the length of te path from root to node1 using pointer1...
similarly find for node2 usng pointer2..
subtract both the pathlengths...
and tat gives how many times the pointer2 from te node2 has to be traversed back towards root....
after this both the pointers will b in te same level...
now just find the parent for either of te nodes...........and tis ll give the common ancestor for both the nodes
node* LCA(node* nd1, node* nd2){
node* cur1 = nd1;
node* cur2 = nd2;
// calculate nd1 height
int nd1_height = 0;
while(cur1->parent!=NULL){
nd1_height++;
cur1 = cur1->parent;
}
// calculate nd2 height
int nd2_height = 0;
while(cur2->parent!=NULL){
nd2_height++;
cur2 = cur2->parent;
}
int diff = nd1_height - nd2_height;
cur1 = nd1;
cur2 = nd2;
if(diff>0){
while(diff--){
cur1 = cur1->parent;
}
} else{
diff = -diff;
while(diff--){
cur2 = cur2->parent;
}
}
while(1){
if(cur1==NULL || cur2==NULL) break;
if(cur1 == cur2)
return cur1;
cur1 = cur1->parent;
cur2 = cur2->parent;
}
return NULL;
}
Tree* ClosestAnscestor(int Rdata, int lData, Tree *node)
{
if(node != NULL)
{
if(findnode(node->left, lData) && findnode(node->right, Rdata))
return node;
else
{
ClosestAnscestor(Rdata,lData,node->left);
ClosestAnscestor(Rdata,lData,node->right);
}
}
else
return NULL;
}
bool findnode(Tree *node, int data)
{
if(node != NULL)
{
if(node->data == data)
return true;
else if(data < node->data)
findnode(node->left, data);
else
findnode(node->right, data);
}
else
return false;
}
struct node *LCA(struct node *R,struct node *c1,struct node *c2)
{
struct node *l,*r;
if(!c1 ||!c2)
return NULL;
if(R->left==c1||R->left==c2||R->right==c1||R->right==c2)
return R;
l=NULL:
r=NULL;
l=LCA(R->left,c1,c2);
r=LCA(R->right,c1,c2);
if(!l && !r)
return NULL;
if(l!=NULL && r!=NULL)
return R;
l=l==NULL?r:l;
return l;
}
while(treenode!=null){
- GKS June 14, 2010if(treenode.data> node1.data && treenode.data<node2.data){
return treenNode;
}else if(treeNode.data < node1.data && treenode.data > node2.data) {
return treeNode;
}else if(treeNode.data > node1.data && treeNode.data > node2.data){
treeNode= treeNode-> left;
}else if(treeNode.data<node2.data && treeNode.data> node1.data){
treeNode=treeNode->right;
}
}