Merging 2 Binary Search Trees

Question

How do you merge 2 Binary Search Trees in such a way that the resultant tree contains all the elements of both the trees and also maintains the BST property.

I saw the solution provided in How to merge two BST's efficiently?

However that solution involves converting into a Double Linked List. I was wondering if there is a more elegant way of doing this which could be done in place without the conversion. I came up with the following pseudocode. Does it work for all cases? Also I am having trouble with the 3rd case.

node* merge(node* head1, node* head2) {         if (!head1)             return head2;         if (!head2)             return head1;          // Case 1.         if (head1->info > head2->info) {             node* temp = head2->right;             head2->right = NULL;             head1->left = merge(head1->left, head2);             head1 = merge(head1, temp);             return head1;         } else if (head1->info < head2->info)  { // Case 2             // Similar to case 1.         } else { // Case 3             // ...         } } 

Answer 1

The two binary search trees (BST) cannot be merged directly during a recursive traversal. Suppose we should merge Tree 1 and Tree 2 shown in the figure.

The recursion should reduce the merging to a simpler situation. We cannot reduce the merging only to the respective left subtrees L1 and L2, because L2 can contain numbers larger than 10, so we would need to include the right subtree R1 into the process. But then we include numbers greater than 10 and possibly greater than 20, so we would need to include the right subtree R2 as well. A similar reasoning shows that we cannot simplify the merging by including subtrees from Tree 1 and from Tree 2 at the same time.

The only possibility for reduction is to simplify only inside the respective trees. So, we can transform the trees to their right spines with sorted nodes:

Now, we can merge the two spines easily into one spine. This spine is in fact a BST, so we could stop here. However, this BST is completely unbalanced, so we transform it to a balanced BST.

The complexity is:

Spine 1: time = O(n1),    space = O(1)  Spine 2: time = O(n2),    space = O(1)  Merge:   time = O(n1+n2), space = O(1)  Balance: time = O(n1+n2), space = O(1)  Total:   time = O(n1+n2), space = O(1) 

The complete running code is on http://ideone.com/RGBFQ. Here are the essential parts. The top level code is a follows:

Node* merge(Node* n1, Node* n2) {     Node *prev, *head1, *head2;        prev = head1 = 0; spine(n1, prev, head1);      prev = head2 = 0; spine(n2, prev, head2);     return balance(mergeSpines(head1, head2)); } 

The auxiliary functions are for the tranformation to spines:

void spine(Node *p, Node *& prev, Node *& head) {        if (!p) return;        spine(p->left, prev, head);        if (prev) prev->right = p;        else head = p;       prev = p;      p->left = 0;       spine(p->right, prev, head);  }  

Merging of the spines:

void advance(Node*& last, Node*& n) {     last->right = n;      last = n;     n = n->right;  }  Node* mergeSpines(Node* n1, Node* n2) {     Node head;     Node* last = &head;     while (n1 || n2) {         if (!n1) advance(last, n2);         else if (!n2) advance(last, n1);         else if (n1->info < n2->info) advance(last, n1);         else if (n1->info > n2->info) advance(last, n2);         else {             advance(last, n1);             printf("Duplicate key skipped %d \n", n2->info);             n2 = n2->right;         }     }     return head.right;  } 

Balancing:

Node* balance(Node *& list, int start, int end) {     if (start > end) return NULL;       int mid = start + (end - start) / 2;         Node *leftChild = balance(list, start, mid-1);        Node *parent = list;     parent->left = leftChild;        list = list->right;        parent->right = balance(list, mid+1, end);        return parent;  }     Node* balance(Node *head) {     int size = 0;     for (Node* n = head; n; n = n->right) ++size;     return balance(head, 0, size-1);  }