# Find the Common Ancestor and Print the Path.

+7 votes
738 views
``````                    10
/  \
7     15
/ \    / \
6   8  12  18
/     \
5       9
(Given Binary tree)
``````
posted Nov 23, 2013
Share this question

Common Ancestor or lowest common ancestor.

## 1 Answer

+1 vote

Here is the working C++ code If it is Lowest common ancestor and Binary tree, The above tree seems to be binary search tree If it is binary search tree it was pretty simple...

``````#include <iostream>
using namespace std;

struct node {
int v;
node* l;
node* r;
node(int v1) : v(v1),l(NULL),r(NULL) {}
};

typedef node* np;

np lca(np rt, int *v, int n1, int n2) {
int lc, rc;
if(rt == NULL) {
*v = 0;
return NULL;
}
if((rt->v == n1) || (rt->v == n2)) {
lca(rt->l, &lc, n1, n2);
if(lc == 1) {
*v = 2;
return rt;
}
else {
lca(rt->r, &rc, n1, n2);
if(rc == 1) {
*v = 2;
return rt;
}
else {
*v = 1;
return NULL;
}
}
}
else {
np k = lca(rt->l, &lc, n1, n2);
if(lc == 2) {
*v = 2;
return k;
}
else if(lc == 1) {
k = lca(rt->r, &rc, n1, n2);
if(rc == 1) {
*v = 2;
return rt;
}
else {
*v = 1;
return NULL;
}
}
else {
k = lca(rt->r, &rc, n1, n2);
if(rc == 2) {
*v = 2;
return k;
}
else if(rc == 1){
*v = 1;
return NULL;
}
else {
*v = 0;
return NULL;
}
}
}
}

int main() {
struct node *root = new node(1);
root->l = new node(2);
root->r = new node(3);
root->l->l = new node(4);
root->l->r = new node(5);
root->r->l = new node(6);
root->r->r = new node(7);
root->l->l->l = new node(8);
root->l->l->r = new node(9);
root->l->r->l = new node(12);
root->r->r->l = new node(10);
root->r->r->l->r = new node(11);
root->l->l->r->l = new node(13);
root->l->l->r->r = new node(14);
root->l->l->r->r->l = new node(15);
int k;
np res = lca(root, &k, 14, 15);
if(res != NULL) cout << res->v << endl;
else cout << "Given two Numbers not present in binary tree" << endl;
}
``````
answer Nov 24, 2013 by
Similar Questions
+7 votes

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

+5 votes
``````      40
/\
20 60
/\  \
10 30  80
/   /\
25  70 90
\
75

longest path
25 30 20 40 60 80 70 75
Answer
25 ----> 75
``````
+7 votes

Print cousins of a given node (Not sibling) ??

+7 votes
``````     50
/  \
20   30
/ \
70  80
/  \   \
10   40  60
``````

printing the border elements anticlockwise direction:
->50->20->70->10->40->60->30