Merging two Binary Search Trees (BSTs) efficiently is a problem that often arises in computer science, particularly when dealing with applications that require maintaining sorted elements rapidly. A Binary Search Tree is a node-based data structure where each node has a key greater than all the keys in its left subtree and less than all the keys in its right subtree. This article will explore how to merge two BSTs into one efficiently, respecting the properties of BSTs.

1. Understanding the Problem

The task of merging two BSTs is to combine them such that the resultant tree is also a BST. Ideally, the combined tree should retain its BST properties, and operations like lookup, insert, and delete should remain efficient.

2. Strategies for Merging BSTs

2.1 In-Order Traversal and Sorting

One straightforward method is to perform an in-order traversal on both BSTs to create two sorted lists of elements. The two lists are then merged into a single sorted list, which is ultimately converted back into a balanced BST.

Steps:

• Perform in-order traversal of both BSTs to get two sorted arrays.
• Merge these two sorted arrays into one.
• Convert the merged array into a balanced BST.

Time Complexity:

• In-order traversal of BST_1: $O(n_1)$
• In-order traversal of BST_2: $O(n_2)$
• Merging of arrays: $O(n_1 + n_2)$
• Construction of balanced BST from array: $O(n_1 + n_2)$

Overall, the time complexity is $O(n_1 + n_2)$.

2.2 Using a Doubly Linked List

Another efficient way involves using tree transformations. Both trees are transformed into sorted doubly linked lists, merged, and then transformed back into a BST.

Steps:

• Transform both BSTs into sorted doubly linked lists.
• Merge the two sorted linked lists.
• Convert the merged linked list back into a balanced BST.

Time Complexity:

• Transforming a BST to a doubly linked list: $O(n)$ per tree
• Merging two linked lists: $O(n_1 + n_2)$
• Construction of balanced BST from linked list: $O(n_1 + n_2)$

This method also has an overall time complexity of $O(n_1 + n_2)$.

3. Detailed Example

Consider two BSTs:

• BST_1:
  1 5
• BST_2:
  2 6
  • BST_1: [1, 3, 5]
  • BST_2: [2, 4, 6]
  • Resulting BST:
    2 5 1 4 6
• One of the BSTs is empty.
• Both BSTs contain overlapping elements.
• Both trees are already balanced or not.