# Merge two sets, list and tree

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?

• You have placed a bounty on this question stating the current answer is out-of-date. In what way is it out-of-date? If you could be more specific as to why you want a new answer, people may respond. – apnorton Feb 1 '15 at 0:04

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} &\verbif(p2 != NULL)\\ &\verb p2=p2->LC\\ &\verbelse\\ &\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)


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)
else
(first, middle) = merge(list, tree->LC)

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