Merge Two Binary Search Trees - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given two binary search trees (BSTs), the goal is to merge them into a single balanced binary search tree. The resulting tree should contain all elements from both BSTs and should maintain the BST property: for every node, values in the left subtree are smaller and values in the right subtree are greater.

You are not allowed to insert elements one by one into the new tree; instead, consider using optimized steps to build the tree.

Examples❯

Tree 1 Tree 2 Merged Output Description
[2, 1, 3]
[5, 4, 6]
[1, 2, 3, 4, 5, 6] In-order traversal of both BSTs: [1,2,3] and [4,5,6], merged and sorted to [1,2,3,4,5,6]
[10, 5, 15]
[20, 16, 25]
[5, 10, 15, 16, 20, 25] In-order of Tree 1: [5,10,15], Tree 2: [16,20,25]. Merged into sorted array.
[] [7, 3, 9]
[3, 7, 9] One tree is empty. Output is just the in-order traversal of Tree 2.
[8, 3, 10, 1, 6, null, 14]
[7, 4, 12]
[1, 3, 4, 6, 7, 8, 10, 12, 14] Combined in-order traversals from both BSTs merged into sorted order.

Visualization Player

Solution❯

Case 1: Normal Trees with Elements

When both binary search trees contain multiple elements, we can perform an in-order traversal on each tree. This traversal gives a sorted array of elements for each BST. Next, merge these two sorted arrays into one using the standard merging technique from merge sort.

The final step is to build a balanced BST from the merged sorted array. This is done by picking the middle element as the root and recursively building the left and right subtrees. This ensures that the tree remains balanced.

For example, Tree1 = [2, 1, 4] gives [1, 2, 4] and Tree2 = [3, 6] gives [3, 6]. Merging them: [1, 2, 3, 4, 6]. Then build a balanced BST using this array.

Case 2: One Tree is Empty

If one of the trees is empty, we can skip traversal and merging for that tree. Simply return the other tree as it is already a valid BST. There’s no need to perform any merging or reconstruction.

For example, Tree1 = [] and Tree2 = [1], the merged result is just [1], which itself is a BST.

Case 3: Both Trees are Empty

If both trees are empty, the result is also an empty tree. There are no elements to process or build into a BST.

This is the base case in recursive solutions and can be handled easily by returning null or an empty list.

Case 4: Trees with Disjoint or Overlapping Ranges

If the values in the trees are completely disjoint (e.g., all values in Tree1 are less than those in Tree2), the merged array remains sorted with no overlap. If there’s an overlap, the merge step ensures the final array maintains sorted order.

For example, Tree1 = [5, 3, 7, 2, 4, 6, 8] and Tree2 = [10, 9, 11] gives merged array [2, 3, 4, 5, 6, 7, 8, 9, 10, 11], and this is used to construct the final balanced BST.

Case 5: Skewed Trees

In cases where one or both trees are skewed (all nodes are either on the left or right), the traversal step will still generate sorted arrays. Hence, the merge and build steps work the same way.

The final BST after construction will be balanced, even if input trees were not.

Algorithm Steps❯

  1. Given two binary search trees, perform an in-order traversal on each tree to obtain two sorted arrays. Use inorder traversal on each tree.
  2. Merge the two sorted arrays into a single sorted array using a merge operation.
  3. Construct a balanced binary search tree from the merged sorted array using a recursive buildBST or sortedArrayToBST function.
  4. The resulting tree is the merged binary search tree.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root, arr):
    if root:
        inorder(root.left, arr)
        arr.append(root.val)
        inorder(root.right, arr)


def mergeArrays(arr1, arr2):
    i = j = 0
    merged = []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged


def sortedArrayToBST(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root


def mergeTwoBSTs(root1, root2):
    arr1, arr2 = [], []
    inorder(root1, arr1)
    inorder(root2, arr2)
    merged = mergeArrays(arr1, arr2)
    return sortedArrayToBST(merged)

# Example usage:
if __name__ == '__main__':
    # BST 1:   2
    #         / \
    #        1   3
    root1 = TreeNode(2, TreeNode(1), TreeNode(3))
    
    # BST 2:   7
    #         / \
    #        6   8
    root2 = TreeNode(7, TreeNode(6), TreeNode(8))
    
    mergedRoot = mergeTwoBSTs(root1, root2)
    result = []
    inorder(mergedRoot, result)
    print(result)