Find the Common Ancestor and Print the Path.

Question

                    10
                    /  \                    
                   7     15
                  / \    / \
                 6   8  12  18
                /     \
               5       9
            (Given Binary tree) 

Comments

Common Ancestor or lowest common ancestor.

Answer 1

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;
}