top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Find the Common Ancestor and Print the Path.

+7 votes
699 views
                    10
                    /  \                    
                   7     15
                  / \    / \
                 6   8  12  18
                /     \
               5       9
            (Given Binary tree) 
posted Nov 23, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
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 Raghu
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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...