Merge two BST 's | Binary Search Tree | GFG POTD | Dry Run & Explanation

[@Veom03]

If You Like the Video then Plzz Consider Subscribing ☺.
CODE:
class Solution {
public:
void store_left(Node* root,stack& st){
Node* curr = root;
while(curr != NULL){
st.push(curr);
curr = curr->left;
}
}
vector merge(Node *root1, Node *root2) {
stack st1,st2;
vector ans;
store_left(root1,st1);
store_left(root2,st2);
while(!st1.empty() && !st2.empty()){
if(st1.top()->data < st2.top()->data){
Node* curr = st1.top();
st1.pop();
ans.push_back(curr->data);
store_left(curr->right,st1);
}
else if(st2.top()->data < st1.top()->data){
Node* curr = st2.top();
st2.pop();
ans.push_back(curr->data);
store_left(curr->right,st2);
}
else{
Node* curr1 = st1.top();
Node* curr2 = st2.top();
st1.pop();
st2.pop();
ans.push_back(curr1->data);
ans.push_back(curr2->data);

store_left(curr1->right,st1);
store_left(curr2->right,st2);
}
}
while(!st1.empty()){
Node* curr1 = st1.top();
st1.pop();
ans.push_back(curr1->data);
store_left(curr1->right,st1);
}
while(!st2.empty()){
Node* curr2 = st2.top();
st2.pop();
ans.push_back(curr2->data);
store_left(curr2->right,st2);
}
return ans;
}
};

[@AVALACHAITANYA]

Nice explanation

[@Veom03]

Glad you liked it 😊.