Merge Two Binary Search Trees - Algorithm, Visualization, Examples

Binary Search Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

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.

Solution❯

Understanding the Problem

We are given two binary search trees (BSTs), and our task is to merge them into a single balanced binary search tree. A BST is a special kind of binary tree where the left subtree has smaller values than the root, and the right subtree has larger values. Merging two BSTs involves collecting all their values, ensuring they are sorted, and then constructing a new BST that is height-balanced.

Step-by-Step Solution with Example

Step 1: In-order Traversal of Both Trees

Perform an in-order traversal on each of the two trees. In-order traversal visits nodes in sorted order (left, root, right). So, for Tree1 = [2, 1, 4], in-order traversal gives [1, 2, 4]. For Tree2 = [3, 6], in-order traversal gives [3, 6].

Step 2: Merge the Two Sorted Arrays

Use a two-pointer merge technique, just like the merge step in merge sort, to combine the two sorted arrays into one sorted array. From the previous step, we merge [1, 2, 4] and [3, 6] to get [1, 2, 3, 4, 6].

Step 3: Build a Balanced BST from Merged Array

Now that we have a sorted array [1, 2, 3, 4, 6], we construct a balanced BST by picking the middle element as the root (which ensures minimal height). Then recursively build the left and right subtrees from the left and right halves of the array.

Step 4: Return the New BST

The constructed tree is a balanced BST that contains all the nodes from both input trees.

Edge Cases

Case 1: One Tree is Empty

If one of the trees is empty, we can skip traversal and merging for that tree. The other tree is already a valid BST, so we return it directly.
Example: Tree1 = [] and Tree2 = [1] → Result: [1]

Case 2: Both Trees are Empty

If both trees are empty, the result is also an empty tree.
This is a base case handled easily by returning null or an empty list.

Case 3: Trees with Disjoint or Overlapping Values

If the ranges of values in both trees do not overlap (e.g., all values in Tree1 < Tree2), the merged array will still be sorted. If values overlap, the merge step maintains sorted order.
Example: Tree1 = [5, 3, 7, 2, 4, 6, 8], Tree2 = [10, 9, 11] → Merged: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Case 4: Skewed Trees

If input trees are skewed (all nodes on one side), they still produce sorted arrays during in-order traversal. The final constructed BST will be balanced regardless of input tree shape.

Finally

This approach is intuitive and modular. It breaks down the problem into manageable parts: traversal, merge, and construction. It also naturally handles edge cases like empty trees or skewed structures. The key idea is transforming trees into sorted arrays and then back into a balanced BST, preserving the correctness and efficiency of BST operations.

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void inorder(TreeNode* root, int* arr, int* index) {
    if (!root) return;
    inorder(root->left, arr, index);
    arr[(*index)++] = root->val;
    inorder(root->right, arr, index);
}

int* mergeArrays(int* arr1, int n1, int* arr2, int n2, int* mergedSize) {
    int* merged = (int*)malloc((n1 + n2) * sizeof(int));
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            merged[k++] = arr1[i++];
        } else {
            merged[k++] = arr2[j++];
        }
    }
    while (i < n1) merged[k++] = arr1[i++];
    while (j < n2) merged[k++] = arr2[j++];
    *mergedSize = k;
    return merged;
}

TreeNode* sortedArrayToBST(int* nums, int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    TreeNode* root = createNode(nums[mid]);
    root->left = sortedArrayToBST(nums, start, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

TreeNode* mergeTwoBSTs(TreeNode* root1, TreeNode* root2) {
    int arr1[100], arr2[100];
    int n1 = 0, n2 = 0;
    inorder(root1, arr1, &n1);
    inorder(root2, arr2, &n2);
    int mergedSize = 0;
    int* mergedArr = mergeArrays(arr1, n1, arr2, n2, &mergedSize);
    TreeNode* root = sortedArrayToBST(mergedArr, 0, mergedSize - 1);
    free(mergedArr);
    return root;
}

// Example usage:
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    printf("%d ", root->val);
    printInorder(root->right);
}

int main() {
    TreeNode* root1 = createNode(2);
    root1->left = createNode(1);
    root1->right = createNode(3);
    TreeNode* root2 = createNode(7);
    root2->left = createNode(6);
    root2->right = createNode(8);
    TreeNode* mergedRoot = mergeTwoBSTs(root1, root2);
    printInorder(mergedRoot);
    printf("\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...