Merge two sets, list and tree

Question

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$.

That's what I have tried:

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

Could you tell me if it is right or if I have done something wrong?

Answer 1

Unfortunately your code is far from perfect, or I am misunderstanding it. If I do understand your intentions, there are multiple places where it could be improved, to name some issues

• In the following code \begin{align} &\verb`if(p2 != NULL)`\\ &\verb` p2=p2->LC`\\ &\verb`else`\\ &\verb` p2=p2->RC` \end{align} the else branch looks up NULL->RC which would cause an error.
• In the first loop you never set new->next.
• In general, either you need to use some additional data structure (like stack or list to remember tree pointers), more loops (to recreate the tree pointers) or recursion; otherwise you won't be able to access all the elements of the tree.

To approach this problem I suggest you should divide it into two parts: making the tree into a list and then merging two list. Some may call such solution suboptimal, but it is simple, natural, and its asymptotic are just as good (even if the constants are a bit worse). To give you a start, the following function appends at the front the contents of a tree tree to a list tail (I'm trying to write in similar style of pseudocode you use, sorry if I got it wrong):

tree_to_list(tree, tail) = 
  if (tree == NULL) return tail
  else
    middle = tree_to_list(tree->RC, tail)
    new_tail = tree_to_list(tree->LC, middle)
    head = newcell(NODE)
    head->data = tree->data
    head->next = new_tail
    return head

Now you only need to write a function that would merge two lists, one given and one obtained from tree_to_list.

On the other hand, if you would insist on doing this without some additional lists, you can make it using a function which takes a list, a tree and returns a pair (first element of a list, an element of the list that corresponds to the last element of the tree). If you would like to follow this approach, to give you a start, consider the following code. It's not complete (some special cases marked by ...) and it has some issues (what would happen if middle in the last branch would be NULL?), but it should give you some general idea.

merge_subprocedure(list, tree)
  if (list == NULL) ...
  else if (tree == NULL) ...
  else
    if (list->data <= tree->data)
      (first, middle) = merge(list->next, tree)
      head = newcell(NODE)
      head->data = list->data
      head->next = first
      return (head, middle)
    else
      head = newcell(NODE)
      head->data = tree->data
      (first, middle) = merge(list, tree->LC)
      head->next = first
      (first2, middle2) = merge(middle->next, tree->RC)
      middle->next = first2
      return (head, middle2)

Finally, I think that stackoverflow would be much better for this question. Nevertheless, I hope this helps $\ddot\smile$