How to Efficiently Merge a Sorted List and a Pre-Order Sorted Tree?

[evinda]

Hi! (Smile)

We are given two sets $S_1$ and $S_2$.
We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree.
I have to write a pseudocode, that implements the operation Merge() of the sets $S_1$ and $S_2$.
The time complexity of the algorithm should be $O(n_1+n_2)$, where $n_1$ is the number of elements of $S_1$ and $n_2$ is the number of elements of $S_2$.Could you give me a hint, how we could do this? (Thinking)

 

[evinda]

Is it maybe like that?

SetMerge(LNODE *S1, TNODE *S2)
      LNODE *p1=S1
      TNODE *p2=S2
      LNODE *S, slast, new
      while(p1 != NULL p2 != NULL)
           new=newcell(NODE)
           if(p2->data < p1->data)
                 new->data=p2->data
                 if(p2 != NULL)
                     p2=p2->LC
                 else
                     p2=p2->RC
           else
                 new->data=p1->data
                 p1=p1->next
      new->next=NULL
      if(S==NULL)
         S=new
         slast=new
      else
         slast->next=new
         slast=new
      while(p1 != NULL)
         new=newcell(NODE)
         new->data=p1->data
         new->next=NULL
         if(S==NULL)
            S=new
            slast=new
         else
            slast->next=new
            slast=new

Or have I done something wrong? (Thinking)