Merge Binary Search Trees

/* Merge Binary Search Trees
 * http://stackoverflow.com/a/7732490
 * Author: Jiri, http://stackoverflow.com/users/805681/jiri
 * Created 11-Oct-2011
 * References:
 * http://stackoverflow.com/questions/7540546/merging-2-binary-search-trees
 * http://dzmitryhuba.blogspot.com/
 * http://cslibrary.stanford.edu/109/
 * http://www.ihas1337code.com/2010/11/convert-binary-search-tree-bst-to.html
 * http://www.ihas1337code.com/2010/11/convert-sorted-list-to-balanced-binary.html
 */

#include <stdio.h>

struct Node {
    int info;
    Node* left;
    Node* right;
};

void insert(Node*& root, int info) {
    if (root == 0) {
        root = new Node();
        root->info = info;
    }
    else if (info < root->info) 
        insert(root->left, info);
    else if (info > root->info) 
        insert(root->right, info);
    else 
        printf("Error: duplicate key %d ignored", info);
}

void printSpine(Node* head) {
    for (Node* current = head; current; current = current->right)
        printf("%d ", current->info);
    printf("\n");
}

void printTree(Node* node, int level) {
    for (int i = 0; i < level; ++i) printf(" ");
    printf("%d\n", node->info);
    if (node->left) 
        printTree(node->left, level + 1);
    if (node->right) 
        printTree(node->right, level + 1);
}

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); 
} 

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); 
} 

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; 
}

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

int main(int argc, char** argv) {
    Node* root1 = 0;    
    insert(root1, 14);
    insert(root1, 12);
    insert(root1, 1);
    insert(root1, 3);
    insert(root1, 56);
    insert(root1, 6);
    insert(root1, 73);
        
    Node* root2 = 0;    
    insert(root2, 4);
    insert(root2, 22);
    insert(root2, 21);
    insert(root2, 13);
    insert(root2, 5);
    insert(root2, 16);
    insert(root2, 7);

    Node* root = merge(root1, root2);
    printTree(root, 0);
    return 0; 
}