# Merge Two Balanced Binary Search Trees

• Merge Two Balanced Binary Search Trees

• @haochenliu
Here is my Solution:
Time Complexity:O(n+m)
Space Complexity:O (height of tree1 + height of tree2)

``````/* The structure of Node is
struct Node {
int data;
Node * right, * left;
};*/

void merge(Node *root1, Node *root2)
{
Node* curr1=NULL;
Node* curr2=NULL;
int flag1=1;
int flag2=1;

stack<Node*> s1,s2;
while(1)
{
//  Like inorder of first Tree
while(flag1)
{
while(root1)
{
s1.push(root1);
root1=root1->left;
}
if(!s1.empty())
{
curr1=s1.top();
s1.pop();
root1=curr1->right;
break;
}
else
{
curr1=NULL;
break;
}
}

//  Like inorder of second Tree
while(flag2)
{
while(root2)
{
s2.push(root2);
root2=root2->left;
}
if(!s2.empty())
{
curr2=s2.top();
s2.pop();
root2=curr2->right;
break;
}
else
{
curr2=NULL;
break;
}
}

// now comparing curr1 and cuur2 and deciding from
//which tree next element will come

if(curr1==NULL && curr2==NULL)
break;
else if(curr1==NULL)
{
cout<<curr2->data<<" ";
flag1=0;
flag2=1;
}
else if(curr2==NULL)
{
cout<<curr1->data<<" ";
flag2=0;
flag1=1;
}
else if(curr1->data>curr2->data)
{
cout<<curr2->data<<" ";
flag1=0;
flag2=1;
}
else
{
cout<<curr1->data<<" ";
flag2=0;
flag1=1;
}

}

cout<<endl;
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.