Merge Two Balanced Binary Search Trees

In this problem, we are given two balanced binary search trees. We have to create a function to merge the two binary search trees into one single search tree. Suppose one of the binary trees has m number of elements, and n is the number of nodes in the second binary tree. We have to create an efficient one that can merge the two binary trees in an optimum time.

Approach - 1

This approach will create a new merged tree out of the two given trees. We will follow these steps to create this tree.

• Firstly, we will define the function that gives us the inorder traversal of a tree. In this way we will get inorder traversal of the two binary search trees. As we know, the inorder traversal of the binary search trees is sorted.
• Then, we will create a function to merge the two sorted arrays. These arrays are the inorder traversal of the given binary search trees. We will merge the two arrays using the linear loop by traversing both of the arrays completely. We will store the merged array in a new array.
• Now we have a merged sorted array, which will work as the inorder traversal of the new binary search tree we must create. Hence, we will define a function that will convert an inorder traversal to a tree.
• This will be our final merged binary search tree.

Here is the Python code of this approach.

Code

Output:

 The first binary search tree is: [2, 5, 7, 10, 30] The second binary search tree is: [4, 8, 12] The Inorder traversal of the merged binary search tree 2 4 5 7 8 10 12 30 

Time complexity: The time complexity of this program is O(m+n), where m and n are the number of nodes in the two binary search trees. We have used linear loops to traverse the two binary trees to store the inorder traversal and merge the two arrays.

Space complexity: The space complexity of this program will be the total space taken by the arrays used to store the inorder traversals of the arrays. The first binary search tree will take O(m) space, and the second will take O(n) space. Hence, the total space complexity is O(m+n).

Approach - 2

This approach will use a Doubly Linked List to create the merged binary search tree. This approach is better than the previous one because the tree will be created in place. These are the steps to solve the problem using this approach:

• We can use a Doubly Linked List to merge trees in place. Following are the steps.
• We will convert the two given binary trees into a doubly linked list data structure.
• Then, we will merge these two doubly linked lists.
• In the last step, we will convert the merged doubly linked list into a binary search tree. This will be our required merged binary search tree.

Code

Output:

 The inorder traversal of the merged binary search tree is: 2 4 5 7 8 10 12 30 

Time Complexity: The time complexity of this program is linear. We have only used linear loops to perform all the required operations. Therefore, the time complexity is O(m + n), where m and n are the number of nodes in the two binary search trees.

Auxiliary Space: We have not used extra space to store the binary tree and the linked lists. Hence, the space complexity of this approach is constant, i.e., O(1).