(EN) A-AA+ Sitemap Search
Snippet so7732490
Back to Overview

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

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;
if (prev)
prev->right = p;
else
prev = p;
p->left = 0;
}

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

int size = 0;
for (Node* n = head; n; n = n->right) ++size;
}

void advance(Node*& last, Node*& n) {
last->right = n;
last = n;
n = n->right;
}

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

Node* merge(Node* n1, Node* n2) {
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;
}
```
```