ProgramGuru

Merge Two Binary Search Trees

Problem and examples

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.

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.

Explore Merge Two Binary Search Trees

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

void inorder(TreeNode* root, vector<int>& arr) {
    if (root) {
        inorder(root->left, arr);
        arr.push_back(root->val);
        inorder(root->right, arr);
    }
}

vector<int> mergeArrays(const vector<int>& arr1, const vector<int>& arr2) {
    vector<int> merged;
    int i = 0, j = 0;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) merged.push_back(arr1[i++]);
        else merged.push_back(arr2[j++]);
    }
    while (i < arr1.size()) merged.push_back(arr1[i++]);
    while (j < arr2.size()) merged.push_back(arr2[j++]);
    return merged;
}

TreeNode* sortedArrayToBST(const vector<int>& nums, int start, int end) {
    if (start > end) return nullptr;
    int mid = (start + end) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums, start, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

TreeNode* mergeTwoBSTs(TreeNode* root1, TreeNode* root2) {
    vector<int> arr1, arr2;
    inorder(root1, arr1);
    inorder(root2, arr2);
    vector<int> merged = mergeArrays(arr1, arr2);
    return sortedArrayToBST(merged, 0, merged.size() - 1);
}

int main() {
    TreeNode* root1 = new TreeNode(2);
    root1->left = new TreeNode(1);
    root1->right = new TreeNode(3);
    TreeNode* root2 = new TreeNode(7);
    root2->left = new TreeNode(6);
    root2->right = new TreeNode(8);
    TreeNode* mergedRoot = mergeTwoBSTs(root1, root2);
    vector<int> result;
    inorder(mergedRoot, result);
    for (int v : result) cout << v << " ";
    cout << endl;
    return 0;
}

Python implementation

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)

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class MergeTwoBSTs {

    public List<Integer> inorder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorderHelper(root, list);
        return list;
    }

    private void inorderHelper(TreeNode root, List<Integer> list) {
        if (root != null) {
            inorderHelper(root.left, list);
            list.add(root.val);
            inorderHelper(root.right, list);
        }
    }

    public List<Integer> mergeArrays(List<Integer> arr1, List<Integer> arr2) {
        List<Integer> merged = new ArrayList<>();
        int i = 0, j = 0;
        while (i < arr1.size() && j < arr2.size()) {
            if (arr1.get(i) < arr2.get(j)) {
                merged.add(arr1.get(i++));
            } else {
                merged.add(arr2.get(j++));
            }
        }
        while (i < arr1.size()) merged.add(arr1.get(i++));
        while (j < arr2.size()) merged.add(arr2.get(j++));
        return merged;
    }

    public TreeNode sortedArrayToBST(List<Integer> nums, int start, int end) {
        if (start > end) return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums.get(mid));
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }

    public TreeNode mergeTwoBSTs(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = inorder(root1);
        List<Integer> list2 = inorder(root2);
        List<Integer> merged = mergeArrays(list1, list2);
        return sortedArrayToBST(merged, 0, merged.size() - 1);
    }

    public static void main(String[] args) {
        MergeTwoBSTs sol = new MergeTwoBSTs();
        // BST 1:  2
        //        / \
        //       1   3
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(3);

        // BST 2:  7
        //        / \
        //       6   8
        TreeNode root2 = new TreeNode(7);
        root2.left = new TreeNode(6);
        root2.right = new TreeNode(8);

        TreeNode mergedRoot = sol.mergeTwoBSTs(root1, root2);
        List<Integer> result = sol.inorder(mergedRoot);
        System.out.println(result);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorder(root, arr) {
    if (root) {
        inorder(root.left, arr);
        arr.push(root.val);
        inorder(root.right, arr);
    }
}

function mergeArrays(arr1, arr2) {
    let i = 0, j = 0;
    const merged = [];
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            merged.push(arr1[i++]);
        } else {
            merged.push(arr2[j++]);
        }
    }
    return merged.concat(arr1.slice(i)).concat(arr2.slice(j));
}

function sortedArrayToBST(nums) {
    if (nums.length === 0) return null;
    const mid = Math.floor(nums.length / 2);
    const root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));
    return root;
}

function mergeTwoBSTs(root1, root2) {
    const arr1 = [];
    const arr2 = [];
    inorder(root1, arr1);
    inorder(root2, arr2);
    const merged = mergeArrays(arr1, arr2);
    return sortedArrayToBST(merged);
}

// Example usage:
const root1 = new TreeNode(2, new TreeNode(1), new TreeNode(3));
const root2 = new TreeNode(7, new TreeNode(6), new TreeNode(8));
const mergedRoot = mergeTwoBSTs(root1, root2);
const result = [];
inorder(mergedRoot, result);
console.log(result);

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func createNode(val int) *TreeNode {
    return &TreeNode{val: val}
}

func inorder(root *TreeNode, arr *[]int) {
    if root != nil {
        inorder(root.left, arr)
        *arr = append(*arr, root.val)
        inorder(root.right, arr)
    }
}

func mergeArrays(arr1, arr2 []int) []int {
    i, j := 0, 0
    merged := []int{}
    for i < len(arr1) && j < len(arr2) {
        if arr1[i] < arr2[j] {
            merged = append(merged, arr1[i])
            i++
        } else {
            merged = append(merged, arr2[j])
            j++
        }
    }
    merged = append(merged, arr1[i:]...)
    merged = append(merged, arr2[j:]...)
    return merged
}

func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    mid := len(nums) / 2
    root := createNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root
}

func mergeTwoBSTs(root1, root2 *TreeNode) *TreeNode {
    arr1 := []int{}
    arr2 := []int{}
    inorder(root1, &arr1)
    inorder(root2, &arr2)
    merged := mergeArrays(arr1, arr2)
    return sortedArrayToBST(merged)
}

func printInorder(root *TreeNode) {
    if root != nil {
        printInorder(root.left)
        fmt.Printf("%d ", root.val)
        printInorder(root.right)
    }
}

func main() {
    root1 := createNode(2)
    root1.left = createNode(1)
    root1.right = createNode(3)

    root2 := createNode(7)
    root2.left = createNode(6)
    root2.right = createNode(8)

    mergedRoot := mergeTwoBSTs(root1, root2)
    printInorder(mergedRoot)
    fmt.Println()
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type TreeLink = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: TreeLink,
    right: TreeLink,
}

impl TreeNode {
    fn new(val: i32) -> TreeLink {
        Some(Rc::new(RefCell::new(TreeNode {
            val,
            left: None,
            right: None,
        })))
    }
}

fn inorder(root: &TreeLink, arr: &mut Vec<i32>) {
    if let Some(node) = root {
        let node = node.borrow();
        inorder(&node.left, arr);
        arr.push(node.val);
        inorder(&node.right, arr);
    }
}

fn merge_arrays(arr1: &Vec<i32>, arr2: &Vec<i32>) -> Vec<i32> {
    let mut i = 0;
    let mut j = 0;
    let mut merged = vec![];

    while i < arr1.len() && j < arr2.len() {
        if arr1[i] < arr2[j] {
            merged.push(arr1[i]);
            i += 1;
        } else {
            merged.push(arr2[j]);
            j += 1;
        }
    }
    merged.extend_from_slice(&arr1[i..]);
    merged.extend_from_slice(&arr2[j..]);
    merged
}

fn sorted_array_to_bst(nums: &[i32]) -> TreeLink {
    if nums.is_empty() {
        return None;
    }
    let mid = nums.len() / 2;
    let root = TreeNode::new(nums[mid]);
    if let Some(ref node) = root {
        node.borrow_mut().left = sorted_array_to_bst(&nums[..mid]);
        node.borrow_mut().right = sorted_array_to_bst(&nums[mid + 1..]);
    }
    root
}

fn merge_two_bsts(root1: TreeLink, root2: TreeLink) -> TreeLink {
    let mut arr1 = vec![];
    let mut arr2 = vec![];
    inorder(&root1, &mut arr1);
    inorder(&root2, &mut arr2);
    let merged = merge_arrays(&arr1, &arr2);
    sorted_array_to_bst(&merged)
}

fn print_inorder(root: &TreeLink) {
    if let Some(node) = root {
        let node = node.borrow();
        print_inorder(&node.left);
        print!("{} ", node.val);
        print_inorder(&node.right);
    }
}

fn main() {
    let root1 = TreeNode::new(2);
    root1.as_ref().unwrap().borrow_mut().left = TreeNode::new(1);
    root1.as_ref().unwrap().borrow_mut().right = TreeNode::new(3);

    let root2 = TreeNode::new(7);
    root2.as_ref().unwrap().borrow_mut().left = TreeNode::new(6);
    root2.as_ref().unwrap().borrow_mut().right = TreeNode::new(8);

    let merged_root = merge_two_bsts(root1, root2);
    print_inorder(&merged_root);
    println!();
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorder(root: TreeNode?, arr: MutableList<Int>) {
    if (root != null) {
        inorder(root.left, arr)
        arr.add(root.val)
        inorder(root.right, arr)
    }
}

fun mergeArrays(arr1: List<Int>, arr2: List<Int>): List<Int> {
    val merged = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] < arr2[j]) {
            merged.add(arr1[i++])
        } else {
            merged.add(arr2[j++])
        }
    }
    merged.addAll(arr1.subList(i, arr1.size))
    merged.addAll(arr2.subList(j, arr2.size))
    return merged
}

fun sortedArrayToBST(nums: List<Int>): TreeNode? {
    if (nums.isEmpty()) return null
    val mid = nums.size / 2
    val root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums.subList(0, mid))
    root.right = sortedArrayToBST(nums.subList(mid + 1, nums.size))
    return root
}

fun mergeTwoBSTs(root1: TreeNode?, root2: TreeNode?): TreeNode? {
    val arr1 = mutableListOf<Int>()
    val arr2 = mutableListOf<Int>()
    inorder(root1, arr1)
    inorder(root2, arr2)
    val merged = mergeArrays(arr1, arr2)
    return sortedArrayToBST(merged)
}

fun printInorder(root: TreeNode?) {
    if (root != null) {
        printInorder(root.left)
        print("${root.val} ")
        printInorder(root.right)
    }
}

fun main() {
    val root1 = TreeNode(2)
    root1.left = TreeNode(1)
    root1.right = TreeNode(3)

    val root2 = TreeNode(7)
    root2.left = TreeNode(6)
    root2.right = TreeNode(8)

    val mergedRoot = mergeTwoBSTs(root1, root2)
    printInorder(mergedRoot)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func inorder(_ root: TreeNode?, _ arr: inout [Int]) {
    guard let root = root else { return }
    inorder(root.left, &arr)
    arr.append(root.val)
    inorder(root.right, &arr)
}

func mergeArrays(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
    var merged = [Int]()
    var i = 0, j = 0
    while i < arr1.count && j < arr2.count {
        if arr1[i] < arr2[j] {
            merged.append(arr1[i])
            i += 1
        } else {
            merged.append(arr2[j])
            j += 1
        }
    }
    merged.append(contentsOf: arr1[i...])
    merged.append(contentsOf: arr2[j...])
    return merged
}

func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
    if nums.isEmpty { return nil }
    let mid = nums.count / 2
    let root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(Array(nums[..<mid]))
    root.right = sortedArrayToBST(Array(nums[(mid+1)...]))
    return root
}

func mergeTwoBSTs(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
    var arr1 = [Int]()
    var arr2 = [Int]()
    inorder(root1, &arr1)
    inorder(root2, &arr2)
    let merged = mergeArrays(arr1, arr2)
    return sortedArrayToBST(merged)
}

func printInorder(_ root: TreeNode?) {
    guard let root = root else { return }
    printInorder(root.left)
    print(root.val, terminator: " ")
    printInorder(root.right)
}

let root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3)

let root2 = TreeNode(7)
root2.left = TreeNode(6)
root2.right = TreeNode(8)

let mergedRoot = mergeTwoBSTs(root1, root2)
printInorder(mergedRoot)

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorder(root: TreeNode | null, arr: number[]): void {
    if (root) {
        inorder(root.left, arr);
        arr.push(root.val);
        inorder(root.right, arr);
    }
}

function mergeArrays(arr1: number[], arr2: number[]): number[] {
    let i = 0, j = 0;
    const merged: number[] = [];
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            merged.push(arr1[i++]);
        } else {
            merged.push(arr2[j++]);
        }
    }
    return merged.concat(arr1.slice(i)).concat(arr2.slice(j));
}

function sortedArrayToBST(nums: number[]): TreeNode | null {
    if (!nums.length) return null;
    const mid = Math.floor(nums.length / 2);
    const root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));
    return root;
}

function mergeTwoBSTs(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    const arr1: number[] = [];
    const arr2: number[] = [];
    inorder(root1, arr1);
    inorder(root2, arr2);
    const merged = mergeArrays(arr1, arr2);
    return sortedArrayToBST(merged);
}

const root1 = new TreeNode(2, new TreeNode(1), new TreeNode(3));
const root2 = new TreeNode(7, new TreeNode(6), new TreeNode(8));
const mergedRoot = mergeTwoBSTs(root1, root2);
const result: number[] = [];
inorder(mergedRoot, result);
console.log(result);