Merge two BSTs

Given two roots of two Binary Search Trees (BST), Find the in-order traversal of merged BSTs.

Examples:

Input:

Output: [1, 2, 3, 4, 5, 6]
Explanation: The inorder traversal after merging the BST will be [1, 2, 3, 4, 5, 6].
Input:

Output: [0, 1, 2, 3, 5, 8, 10]
Explanation: The inorder traversal after merging the BST will be [0, 1, 2, 3, 5, 8, 10]

Try it on GfG Practice

Table of Content

[Approach - 1] Using Array - O(n + m) time and O(n + m) space
[Approach - 2] Using Stack - O(n + m) time and O(n + m) space

[Approach - 1] Using Array - O(n + m) Time and O(n + m) Space

The idea is to perform inorder traversal of both BSTs to get their elements in sorted order, store them in two arrays (or lists), and then merge these two sorted arrays using a two-pointer approach to produce a single sorted list containing all elements from both BSTs.

C++

//Driver Code Starts
#include<iostream>
#include<vector>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* left, *right;
    Node (int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};
//Driver Code Ends


// Function to perform inorder traversal of a BST
// Stores elements in sorted order in the given vector
void inorder(Node* root, vector<int>& arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->data);
    inorder(root->right, arr);
}

// Function to merge two sorted arrays into one sorted array
vector<int> mergeArrays(vector<int>& arr1, vector<int>& arr2) {
    vector<int> result;
    int i = 0, j = 0;
    
    // Traverse both arrays and pick the smaller element
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] <= arr2[j]) {
            result.push_back(arr1[i++]);
        } 
        else {
            result.push_back(arr2[j++]);
        }
    }
    
    while (i < arr1.size()) result.push_back(arr1[i++]);
    
    while (j < arr2.size()) result.push_back(arr2[j++]);
    
    return result;
}

// Function to merge elements of two BSTs into a single sorted list
vector<int> merge(Node *root1, Node *root2) {
    vector<int> arr1, arr2;
    
    // Get inorder traversal of both BSTs
    inorder(root1, arr1);
    inorder(root2, arr2);
    
    return mergeArrays(arr1, arr2);
}


//Driver Code Starts
int main() {
    
    // Create binary tree 1
    //           3
    //         /   \
    //       1      5
    Node* root1 = new Node(3);
    root1->left = new Node(1);
    root1->right = new Node(5);
    
    // Create binary tree 2
    //           4
    //         /   \
    //       2      6
    Node* root2 = new Node(4);
    root2->left = new Node(2);
    root2->right = new Node(6);
    
    vector<int> res = merge(root1, root2);
    for (auto val: res) cout << val << " ";
    cout << endl;
    return 0;
}
//Driver Code Ends

Java

//Driver Code Starts
import java.util.ArrayList;

// Node structure
class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GFG {
//Driver Code Ends

    
    // Function to perform inorder traversal of a BST
    // Stores elements in sorted order in the given list
    static void inorder(Node root, ArrayList<Integer> arr) {
        if (root == null) return;
        inorder(root.left, arr);
        arr.add(root.data);
        inorder(root.right, arr);
    }
    
    // Function to merge two sorted lists into one sorted list
    static ArrayList<Integer> mergeArrays(ArrayList<Integer> arr1, 
                                          ArrayList<Integer> arr2) {
        ArrayList<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        
        // Traverse both lists and pick the smaller element
        while (i < arr1.size() && j < arr2.size()) {
            if (arr1.get(i) <= arr2.get(j)) {
                result.add(arr1.get(i++));
            } 
            else {
                result.add(arr2.get(j++));
            }
        }
        
        while (i < arr1.size()) result.add(arr1.get(i++));
        
        while (j < arr2.size()) result.add(arr2.get(j++));
        
        return result;
    }
    
    // Function to merge elements of two BSTs into a single sorted list
    static ArrayList<Integer> merge(Node root1, Node root2) {
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();
        
        // Get inorder traversal of both BSTs
        inorder(root1, arr1);
        inorder(root2, arr2);
        
        return mergeArrays(arr1, arr2);
    }


//Driver Code Starts
    public static void main(String[] args) {
        
        // Create binary tree 1
        //           3
        //         /   \
        //       1      5
        Node root1 = new Node(3);
        root1.left = new Node(1);
        root1.right = new Node(5);
        
        // Create binary tree 2
        //           4
        //         /   \
        //       2      6
        Node root2 = new Node(4);
        root2.left = new Node(2);
        root2.right = new Node(6);
        
        ArrayList<Integer> res = merge(root1, root2);
        for (int val : res) System.out.print(val + " ");
        System.out.println();
    }
}
//Driver Code Ends

Python

#Driver Code Starts
#  Node structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
#Driver Code Ends


# Function to perform inorder traversal of a BST
# Stores elements in sorted order in the given list
def inorder(root, arr):
    if not root:
        return
    inorder(root.left, arr)
    arr.append(root.data)
    inorder(root.right, arr)

# Function to merge two sorted lists into one sorted list
def mergeArrays(arr1, arr2):
    result = []
    i = j = 0
    
    # Traverse both lists and pick the smaller element
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
            
    while i < len(arr1):
        result.append(arr1[i])
        i += 1
        
    while j < len(arr2):
        result.append(arr2[j])
        j += 1
        
    return result

# Function to merge elements of two BSTs into a single sorted list
def merge(root1, root2):
    arr1, arr2 = [], []
    
    # Get inorder traversal of both BSTs
    inorder(root1, arr1)
    inorder(root2, arr2)
    
    return mergeArrays(arr1, arr2)


#Driver Code Starts
if __name__ == "__main__":
    
    # Create binary tree 1
    #           3
    #         /   \
    #       1      5
    root1 = Node(3)
    root1.left = Node(1)
    root1.right = Node(5)
    
    # Create binary tree 2
    #           4
    #         /   \
    #       2      6
    root2 = Node(4)
    root2.left = Node(2)
    root2.right = Node(6)
    
    res = merge(root1, root2)
    for val in res:
        print(val, end=" ")
    print()
#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

// Node structure
class Node {
    public int data;
    public Node left, right;
    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GFG {
//Driver Code Ends

    
    // Function to perform inorder traversal of a BST
    // Stores elements in sorted order in the given list
    static void inorder(Node root, List<int> arr) {
        if (root == null) return;
        inorder(root.left, arr);
        arr.Add(root.data);
        inorder(root.right, arr);
    }
    
    // Function to merge two sorted lists into one sorted list
    static List<int> mergeArrays(List<int> arr1, List<int> arr2) {
        List<int> result = new List<int>();
        int i = 0, j = 0;
        
        // Traverse both lists and pick the smaller element
        while (i < arr1.Count && j < arr2.Count) {
            if (arr1[i] <= arr2[j]) {
                result.Add(arr1[i++]);
            } 
            else {
                result.Add(arr2[j++]);
            }
        }
        
        while (i < arr1.Count) result.Add(arr1[i++]);
        
        while (j < arr2.Count) result.Add(arr2[j++]);
        
        return result;
    }
    
    // Function to merge elements of two BSTs into a single sorted list
    static List<int> merge(Node root1, Node root2) {
        List<int> arr1 = new List<int>();
        List<int> arr2 = new List<int>();
        
        // Get inorder traversal of both BSTs
        inorder(root1, arr1);
        inorder(root2, arr2);
        
        return mergeArrays(arr1, arr2);
    }


//Driver Code Starts
    static void Main() {
        
        // Create binary tree 1
        //           3
        //         /   \
        //       1      5
        Node root1 = new Node(3);
        root1.left = new Node(1);
        root1.right = new Node(5);
        
        // Create binary tree 2
        //           4
        //         /   \
        //       2      6
        Node root2 = new Node(4);
        root2.left = new Node(2);
        root2.right = new Node(6);
        
        List<int> res = merge(root1, root2);
        foreach (int val in res) Console.Write(val + " ");
        Console.WriteLine();
    }
}
//Driver Code Ends

JavaScript

//Driver Code Starts
// Node structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}
//Driver Code Ends


// Function to perform inorder traversal of a BST
// Stores elements in sorted order in the given array
function inorder(root, arr) {
    if (!root) return;
    inorder(root.left, arr);
    arr.push(root.data);
    inorder(root.right, arr);
}

// Function to merge two sorted arrays into one sorted array
function mergeArrays(arr1, arr2) {
    let result = [];
    let i = 0, j = 0;
    
    // Traverse both arrays and pick the smaller element
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            result.push(arr1[i++]);
        } 
        else {
            result.push(arr2[j++]);
        }
    }
    
    while (i < arr1.length) result.push(arr1[i++]);
    
    while (j < arr2.length) result.push(arr2[j++]);
    
    return result;
}

// Function to merge elements of two BSTs into a single sorted array
function merge(root1, root2) {
    let arr1 = [], arr2 = [];
    
    // Get inorder traversal of both BSTs
    inorder(root1, arr1);
    inorder(root2, arr2);
    
    return mergeArrays(arr1, arr2);
}


//Driver Code Starts
// Driver Code

// Create binary tree 1
//           3
//         /   \
//       1      5
let root1 = new Node(3);
root1.left = new Node(1);
root1.right = new Node(5);

// Create binary tree 2
//           4
//         /   \
//       2      6
let root2 = new Node(4);
root2.left = new Node(2);
root2.right = new Node(6);

let res = merge(root1, root2);
console.log(res.join(" "));
//Driver Code Ends

Output

1 2 3 4 5 6

[Approach - 2] Using Stack - O(n + m) Time and O(n + m) Space

The idea is to simulate the inorder traversal of both trees simultaneously using two stacks, comparing the current minimum elements from both trees at each step and selecting the smaller one to add to the result.

Step by step approach:

Push all left nodes of both trees onto their respective stacks until reaching leftmost nodes.
Compare the top elements of both stacks to determine which has smaller value.
Pop the smaller element, add it to result, and move to its right subtree.
Repeat the process until both stacks are empty and no more nodes to process.

Why using Stack?

We can’t use recursion here because it’s not possible to traverse both trees simultaneously — recursion can only process one call stack at a time. In other words, we can’t pause recursion in one tree, switch to the other, and then resume.
To handle both traversals together and compare nodes dynamically (for example, to stop when one node’s value exceeds the other’s), we use an iterative approach with stacks.

C++

//Driver Code Starts
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* left, *right;
    Node (int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};
//Driver Code Ends


vector<int> merge(Node *root1, Node *root2) {
    vector<int> res;
    stack<Node*> s1, s2;
    
    while (root1 || root2 || !s1.empty() || !s2.empty()) {
        
        // move to the leftmost nodes(min values)
        while (root1) {
            s1.push(root1);
            root1 = root1->left;
        }
        
        while (root2) {
            s2.push(root2);
            root2 = root2->left;
        }
        
        // compare the top element and remove 
        // it and move to its right child
        if (s2.empty() || (!s1.empty() && s1.top()->data <= s2.top()->data)) {
            root1 = s1.top();
            s1.pop();
            res.push_back(root1->data);
            root1 = root1->right;
        } 
        else {
            root2 = s2.top();
            s2.pop();
            res.push_back(root2->data);
            root2 = root2->right;
        }
    }
    return res;
}


//Driver Code Starts
int main() {
    
    // Create binary tree 1
    //           3
    //         /   \
    //       1      5
    Node* root1 = new Node(3);
    root1->left = new Node(1);
    root1->right = new Node(5);
    
    // Create binary tree 2
    //           4
    //         /   \
    //       2      6
    Node* root2 = new Node(4);
    root2->left = new Node(2);
    root2->right = new Node(6);
    
    vector<int> res = merge(root1, root2);
    for (auto val: res) cout << val << " ";
    cout << endl;
    return 0;
}
//Driver Code Ends