1. Overview

A binary search tree (BST) is a fundamental data structure and is a type of binary tree where the value of a left node is less than the parent and the value of a right node is greater than the parent.

In this tutorial, we’re going to learn about two algorithms that can be used to merge two binary search trees. Also, we’ll discuss the complexity a.k.a Big O of these algorithms. The complexity of an algorithm is extremely important as it measures the amount of time and space required to run the algorithm.

There are two binary search trees (BST1 and BST2) in the following image. The merging of these two trees will produce merged BST as shown below:

Merged BST has all the elements of BST1 and BST2 and maintains the characteristics of a binary search tree.

2. Merge, Sort, Reconstruct

In this algorithm, the main idea is to move the elements of both BSTs to an array, sort and form the merged BST.

This algorithm has the following 3 primary steps:

  • step 1: Process the BSTs and store the elements in their respective arrays.
  • step 2: Combine the arrays in a merged array and sort the elements in them. We can use any of the popular sorting methods such as bubble sort, insertion sort, etc.
  • step 3: Copy the elements of the merged array to create merged BST by in-order traversing.

Since it increases with the size of the dataset, the complex it of step 1 is O(n1 + n2). The n1 and n2 are being the size of the BSTs that are merged.

The time complexity of step 2 depends on the type of the sorting algorithm used, it’ll be O(n^2) if it’s bubble sort and O(n log n) if it’s insertion sort.

We need to store all elements in the array, so the space complexity of the step is O(n).

The algorithm can be describe as follows:

Rendered by QuickLaTeX.com

3. Traverse, Sort, Reconstruct

In this solution, we traverse the elements for both BSTs simultaneously and moved to the merged array.

This algorithm also has the following 4 primary steps:

  • step 1: Process the BSTs and store the elements in their respective arrays.
  • step 2: Create an array that has the size of n1 + n2, where n1 and n2 is the size of two of the BSTs that are being merged. This array will store elements of merged BSTs.
  • step 3: Simultaneously traverse both arrays. While traversing, pick the smaller of the current elements and moved it to the merged array. Then progress with processing after removing the element that was picked earlier.
  • step 4: Copy the elements of the merged array to create merged BST by in-order traversing

The time and space complexity of step 1 and step 2 is O(n1 + n2) as the complexity increases with the size of the dataset.

The time complexity of step 3 is O(n1*log(n1) + n2*log (n2)). The space complexity of the step is O(n), where n is the size of the dataset after arrays are merged.

The time and space complexity of step 4 is O(n).

Let’s see how it looks like:

Rendered by QuickLaTeX.com

4. Conclusion

In this article, we looked at two possible solutions that can be used to merge binary search trees. Also, we identified the time and space complexity of each.

guest
0 Comments
Inline Feedbacks
View all comments