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]
[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
//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
#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
//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
[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
//Driver Code Starts
import java.util.ArrayList;
import java.util.Stack;
// Node structure
class Node {
int data;
Node left, right;
Node(int x) {
data = x;
left = null;
right = null;
}
}
class GFG {
//Driver Code Ends
static ArrayList<Integer> merge(Node root1, Node root2) {
ArrayList<Integer> res = new ArrayList<>();
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
while (root1 != null || root2 != null || !s1.empty() || !s2.empty()) {
// move to the leftmost nodes(min values)
while (root1 != null) {
s1.push(root1);
root1 = root1.left;
}
while (root2 != null) {
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.peek().data <= s2.peek().data)) {
root1 = s1.pop();
res.add(root1.data);
root1 = root1.right;
}
else {
root2 = s2.pop();
res.add(root2.data);
root2 = root2.right;
}
}
return res;
}
//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
#Driver Code Starts
# Node structure
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
#Driver Code Ends
def merge(root1, root2):
res = []
s1 = []
s2 = []
while root1 or root2 or s1 or s2:
while root1:
# move to the leftmost nodes(min values)
s1.append(root1)
root1 = root1.left
while root2:
s2.append(root2)
root2 = root2.left
# compare the top element and remove
# it and move to its right child
if not s2 or (s1 and s1[-1].data <= s2[-1].data):
root1 = s1.pop()
res.append(root1.data)
root1 = root1.right
else:
root2 = s2.pop()
res.append(root2.data)
root2 = root2.right
return res
#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
static List<int> merge(Node root1, Node root2) {
List<int> res = new List<int>();
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
while (root1 != null || root2 != null ||
s1.Count > 0 || s2.Count > 0) {
// move to the leftmost nodes(min values)
while (root1 != null) {
s1.Push(root1);
root1 = root1.left;
}
while (root2 != null) {
s2.Push(root2);
root2 = root2.left;
}
// compare the top element and remove
// it and move to its right child
if (s2.Count == 0 || (s1.Count > 0 && s1.Peek().data <= s2.Peek().data)) {
root1 = s1.Pop();
res.Add(root1.data);
root1 = root1.right;
}
else {
root2 = s2.Pop();
res.Add(root2.data);
root2 = root2.right;
}
}
return res;
}
//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
//Driver Code Starts
// Node structure
class Node {
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
//Driver Code Ends
function merge(root1, root2) {
let res = [];
let s1 = [];
let s2 = [];
while (root1 || root2 || s1.length > 0 || s2.length > 0) {
while (root1) {
// move to the leftmost nodes(min values)
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.length === 0 || (s1.length > 0 &&
s1[s1.length-1].data <= s2[s2.length-1].data)) {
root1 = s1.pop();
res.push(root1.data);
root1 = root1.right;
}
else {
root2 = s2.pop();
res.push(root2.data);
root2 = root2.right;
}
}
return res;
}
//Driver Code Starts
// 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);
//Driver Code Ends
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem