find least common ancestor in Binary search tree

Q)least common ancestor for binary search tree

recursive way of doing is here. In BST, all values lesser than root will be on left subtree, values greater than root will be on right subtree.

node *ancestor=NULL

node * LCA(node *root,node *n1, node*n2)
{

if(n1 == NULL && n2 == NULL)
  return root ;

if(n1 == NULL)
 return n2;

if(n2==NULL)
  return  n1 ;

return findLCA(root,n1,n2) ;
}

node *findLCA(node *root,node *n1,node *n2)
{
ancestor=root;

if(n1->data < root->data && n2->data < root->data)
 return LCA(root->left,n1,n2)
else if(n1->data > root->data && n2->data > root->data )
return LCA(root->right,n1,n2)
else
return ancestor;

}

Binary tree Questions

1) how to merge two Binary search trees

A) convert the each binary tree to Single LL using inorder traversal
merge two LL and copy to array.

construct binary tree with mid element as root. if you want to balance tree then we can use AVL tree rotations.

node *prev=NULL;
node *head=NULL:

converttoLL(Treenode *root,node **head)
{
if(root !=NULL)
{
converttoLL(root->left,&head)

if( *head==NULL )
*head=prev=(node *)root;
else{
prev->next=root;
prev=root;
}

convertoLL(root->right,&head)

}//..end if(root !=NULL)
}

constructroot(Treenode *&root,int mid)
{
Treenode *temp=new Treenode();
temp->data=mid;
temp->left=null;
temp->right=null;
root=temp;

}

constructtree(Treenode *&root, int element)
{
Treenode *curr=root;

while(curr!=NULL)
{
 if(curr->data <= element )
curr=curr->left;
else
curr=curr->right;
}

Treenode *temp=new Treenode();
temp->data=mid;
temp->left=null;
temp->right=null;

curr=temp;

}

int main(){

// main method
node *head1=NULL ;
node *head2=NULL;

ConverttoLL(Tree1,&head1);
ConverttoLL(Tree2,&head2);

node *n2=head2;
while(n2!=NULL)
{
node *save=n2->next ;
merge( &head1 , n2 ) ;
n2=save;
}
code for merge is in
http://techie-builder.blogspot.in/2012/06/linked-lists-questions.html

node *n1=head1;
int a[100];
int i=0;

while(n1!=NULL)
{
a[i]=n1->data ;
i++;
n1=n1->next ;
}

constructroot(a[i/2]);

for(int j=0;j < i ; j++ )
{
if(j!=i/2) // already we constructed root
constructtree(a[j]);
}


}