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


}