How to merge two BST's efficiently?

algorithm, binary-search-tree, c++, data-structures, merge

Solution

Naaff's answer with a little more details:

- Flattening a BST into a sorted list is O(N)

- It's just "in-order" iteration on the whole tree.

- Doing it for both is O(n1+n2)

- Merging two sorted lists is into one sorted list is O(n1+n2).

- Keep pointers to the heads of both lists

- Pick the smaller head and advance its pointer

- This is how the merge of merge-sort works

- Creating a perfectly balanced BST from a sorted list is O(N)

- See code snippet below for algorithm[1]

- In our case the sorted list is of size n1+n2. so O(n1+n2)

- The resulting tree would be the conceptual BST of binary searching the list

Three steps of O(n1+n2) result in O(n1+n2)

For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))

[1] Algorithm for creating a balanced BST from a sorted list (in Python):

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}

Problem

How to merge two binary search trees maintaining the property of BST? If we decide to take each element from a tree and insert it into the other, the complexity of this method would be `O(n1 * log(n2))`, where `n1` is the number of nodes of the tree (say `T1`), which we have splitted, and `n2` is the number of nodes of the other tree (say `T2`). After this operation only one BST has `n1 + n2` nodes. My question is: can we do any better than O(n1 * log(n2))?

Original source