Skip to content

Instantly share code, notes, and snippets.

@bkb181
Created July 10, 2020 11:05
Show Gist options
  • Save bkb181/aeeeabc98a8ab83f7a4907e3ef6d754e to your computer and use it in GitHub Desktop.
Save bkb181/aeeeabc98a8ab83f7a4907e3ef6d754e to your computer and use it in GitHub Desktop.
void merge_bst(node* root1, node* root2)
{
stack<node * > s1;
stack<node * > s2;
vector<int> res;
node * temp1= root1;
node * temp2= root2;
while(temp1!=NULL){
s1.push(temp1);
temp1= temp1->left;
}
while(temp2!=NULL)
{
s2.push(temp2);
temp2= temp2->left;
}
while(!s1.empty()&& ! s2.empty())
{
if(s1.top()->data<= s2.top()->data)
{
res.push_back(s1.top()->data);
temp1= s1.top()->right;
s1.pop();
while(temp1!=NULL)
{
s1.push(temp1);
temp1= temp1->left;
}
}
else
{
res.push_back(s2.top()->data);
temp1= s2.top()->right;
s2.pop();
while(temp1!=NULL)
{
s2.push(temp1);
temp1= temp1->left;
}
}
}
while(!s1.empty())
{
res.push_back(s1.top()->data);
temp1= a.top()->right;
s1.pop();
while(temp1!=NULL)
{
s1.push(temp1);
temp1= temp1->left;
}
}
while(!s2.empty())
{
res.push_back(b.top()->data);
temp1= s2.top()->right;
s2.pop();
while(temp1!=NULL)
{
s2.push(temp1);
temp1 = temp1->left;
}
}
print(res);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment