Merge BST Code failing

#1

This code is having a Runtime error. Please explain why.
This has O(n+m) time and O(h1+h2) space complexity.

vector<int> merge(Node *r1, Node *r2)
{
   //Your code here
   stack<Node*> st1,st2;
   vector<int> v;
   
   while(r1){
       st1.push(r1);
       r1 = r1->left;
   }
   while(r2){
       st2.push(r2);
       r2 = r2->left;
   }
   
   while(!st1.empty() && !st2.empty()){
       if(st1.top()->data < st2.top()->data){
           if(!st1.empty()){Node* top = st1.top();
           st1.pop();
           v.push_back(top->data);
           if(top->right){
               st1.push(top->right);
                while(top->left){
                   st1.push(top->left);
                }  
           }} 
       }else{
           if(!st2.empty()){Node* top = st2.top();
           st2.pop();
           v.push_back(top->data);
           if(top->right){
               st2.push(top->right);
                while(top->left){
                   st2.push(top->left);
                }  
           }} 
       }
   }
   return v;
}
#2

And

Are running infinitely hence runtime error :slight_smile:

#3 
vector<int> merge(Node *r1, Node *r2)
{
   //Your code here
   stack<Node*> st1,st2;
   vector<int> v;
   
   while(r1){
       st1.push(r1);
       r1 = r1->left;
   }
   while(r2){
       st2.push(r2);
       r2 = r2->left;
   }
   
   while(!st1.empty() && !st2.empty()){
       if(st1.top()->data < st2.top()->data){
           Node* top = st1.top();
           st1.pop();
           v.push_back(top->data);
           if(top->right){
               st1.push(top->right);
               top = top->right;
                while(top->left){
                   st1.push(top->left);
                   top = top->left;
                }  
           } 
       }else{
           Node* top = st2.top();
           st2.pop();
           v.push_back(top->data);
           if(top->right){
               st2.push(top->right);
               top = top->right;
                while(top->left){
                   st2.push(top->left);
                   top = top->left;
                }  
           }
       }
   }
   while(!st1.empty()){
       v.push_back(st1.top()->data);
       st1.pop();
   }
   while(!st2.empty()){
       v.push_back(st2.top()->data);
       st2.pop();
   }
   return v;
}

rectifying above mentioned issue still gives WA on several cases

#4

There is logical error here
Assume 1 tree to be empty and other containing nodes
And then write for this part
You are only considering Left side nodes here

#5

thanks for help. I missed that part :joy:

1 Like
#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.