15 Jan 2015

e-Khaliyan

Least Common Ancestor - Binary Search Tee

Least Common Ancestor 


1. Iterative 

/* Lowest common Ancesstors */
void lca_non_rec(btptr t, int a, int b)
{
   btptr temp=t;
   while(temp!=NULL)
   {
       if (a < temp->data && b<temp->data)
        temp=temp->left;
       else if (a > temp->data && b > temp->data)
        temp=temp->right;
       else
       {
           cout<<"common anccesstor="<<temp->data; break;
       }
   }
}

2. Recursive 

btptr  lca(btptr t, int a, int b)
{
      if (t!= NULL)
      {
          if (a <t->data && b<t->data)
            return (lca(t->left,a,b));
          else if (a > t->data && b > t->data)
            return (lca(t->right, a, b));
          return (t);
      }
}