Log inSign up
mediumGeeksforGeeksNot Started

Merge Two BSTs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two Binary Search Trees (BSTs), return a combined sorted list of all elements present in both BSTs.

For example: BST 1: [3, 5, 1] -> inorder: [1, 3, 5] BST 2: [4, 6, 2] -> inorder: [2, 4, 6] Merged Result: [1, 2, 3, 4, 5, 6]

Constraints:

  • 1 <= Number of nodes in BST1, BST2 <= 105
  • 1 <= Node.data <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Convert tree traversal into streaming sorted sequences.
  • Implement simultaneous dual-stack iterative inorder traversals.
  • Optimize auxiliary space from O(N1 + N2) down to O(H1 + H2).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Combine two BSTs into a sorted list or balanced BST.
  • Merge sorted sequences from tree sources.
  • Stream merge using two stacks.

Algorithmic Decision Tree:

  • If O(N) memory is fine -> Extract two arrays and merge in O(N1 + N2).
  • If O(H) memory requested -> Dual-stack simultaneous iterative inorder traversal.

Connected Patterns:

Binary Search Tree IteratorMerge Sorted ArrayBalance a Binary Search Tree

1. Collect All Elements & Sort (O((N1+N2) log(N1+N2)))

Intuition

Visit all nodes in both trees and append their values into a single array. Sort the combined array using QuickSort or MergeSort. Takes O((N1 + N2) log(N1 + N2)) time and O(N1 + N2) space.

When to apply: Baseline comparison ignoring BST sorted properties.

Algorithm

  1. Traverse both trees using preorder/DFS, append all values to a list, and sort using a standard sorting algorithm.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9 Node(int val) : data(val), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 void collect(Node* root, std::vector<int>& vals) {
14 if (!root) return;
15 vals.push_back(root->data);
16 collect(root->left, vals);
17 collect(root->right, vals);
18 }
19public:
20 std::vector<int> merge(Node* root1, Node* root2) {
21 std::vector<int> vals;
22 collect(root1, vals);
23 collect(root2, vals);
24 std::sort(vals.begin(), vals.end());
25 return vals;
26 }
27};
28
29int main() {
30 Node* root1 = new Node(3);
31 root1->left = new Node(1);
32 root1->right = new Node(5);
33
34 Node* root2 = new Node(4);
35 root2->left = new Node(2);
36 root2->right = new Node(6);
37
38 Solution sol;
39 std::vector<int> res = sol.merge(root1, root2);
40 for (int v : res) std::cout << v << " ";
41 std::cout << std::endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O((N1 + N2) log(N1 + N2))
  • Space complexity: O(N1 + N2)

2. Two-Pass Inorder Flatten + Two-Pointer Merge

Intuition

1. Perform inorder traversal on BST1 to get sorted array a1. 2. Perform inorder traversal on BST2 to get sorted array a2. 3. Merge a1 and a2 using two pointers i and j in linear O(N1 + N2) time. Total time is O(N1 + N2) and auxiliary space is O(N1 + N2).

When to apply: Standard approach when O(N1 + N2) auxiliary space is acceptable.

Algorithm

  1. Extract sorted arrays from both BSTs via inorder traversal in O(N1 + N2) time, then merge using two pointers in O(N1 + N2) time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct Node {
5 int data;
6 Node* left;
7 Node* right;
8 Node(int val) : data(val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(Node* root, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, vals);
15 vals.push_back(root->data);
16 inorder(root->right, vals);
17 }
18public:
19 std::vector<int> merge(Node* root1, Node* root2) {
20 std::vector<int> a1, a2;
21 inorder(root1, a1);
22 inorder(root2, a2);
23
24 std::vector<int> merged;
25 int i = 0, j = 0;
26 while (i < (int)a1.size() && j < (int)a2.size()) {
27 if (a1[i] <= a2[j]) merged.push_back(a1[i++]);
28 else merged.push_back(a2[j++]);
29 }
30 while (i < (int)a1.size()) merged.push_back(a1[i++]);
31 while (j < (int)a2.size()) merged.push_back(a2[j++]);
32
33 return merged;
34 }
35};
36
37int main() {
38 Node* root1 = new Node(3);
39 root1->left = new Node(1);
40 root1->right = new Node(5);
41
42 Node* root2 = new Node(4);
43 root2->left = new Node(2);
44 root2->right = new Node(6);
45
46 Solution sol;
47 std::vector<int> res = sol.merge(root1, root2);
48 for (int v : res) std::cout << v << " ";
49 std::cout << std::endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(N1 + N2)
  • Space complexity: O(N1 + N2)

3. Dual-Stack Streaming Inorder Merge (O(H1 + H2) Space)

Intuition

Maintain two stacks s1 and s2 for BST1 and BST2. Push left spines for both trees onto their respective stacks. At each step, compare the top node of s1 and s2. Pop the node with the smaller value, append its value to the output list, and advance that tree's pointer into its right subtree (pushing its left spine). Continue until both stacks and pointers are exhausted.

When to apply: Optimal when memory is constrained to tree heights O(H1 + H2).

Algorithm

  1. Simulate inorder traversal on both BSTs simultaneously using two explicit stacks; pop and merge on the fly without storing intermediate arrays.

Dual-Stack Streaming Merge Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Pop 1 from s1
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
s1 = [3, 1], s2 = [4, 2]. Compare 1 <= 2.
Decision / next transition
1
Why this step matters

Pop 1 from s1. Add 1 to result. c1 = 1.right (null).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9 Node(int val) : data(val), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13public:
14 std::vector<int> merge(Node* root1, Node* root2) {
15 std::vector<int> result;
16 std::stack<Node*> s1, s2;
17 Node* c1 = root1;
18 Node* c2 = root2;
19
20 while (c1 || c2 || !s1.empty() || !s2.empty()) {
21 while (c1) {
22 s1.push(c1);
23 c1 = c1->left;
24 }
25 while (c2) {
26 s2.push(c2);
27 c2 = c2->left;
28 }
29
30 if (s2.empty() || (!s1.empty() && s1.top()->data <= s2.top()->data)) {
31 c1 = s1.top();
32 s1.pop();
33 result.push_back(c1->data);
34 c1 = c1->right;
35 } else {
36 c2 = s2.top();
37 s2.pop();
38 result.push_back(c2->data);
39 c2 = c2->right;
40 }
41 }
42
43 return result;
44 }
45};
46
47int main() {
48 Node* root1 = new Node(3);
49 root1->left = new Node(1);
50 root1->right = new Node(5);
51
52 Node* root2 = new Node(4);
53 root2->left = new Node(2);
54 root2->right = new Node(6);
55
56 Solution sol;
57 std::vector<int> res = sol.merge(root1, root2);
58 for (int v : res) std::cout << v << " ";
59 std::cout << std::endl;
60 return 0;
61}

Time & Space Complexity

  • Time complexity: O(N1 + N2)
  • Space complexity: O(H1 + H2) stack space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Collect All Elements & Sort (O((N1+N2) log(N1+N2)))O((N1 + N2) log(N1 + N2))O(N1 + N2)Traverse both trees using preorder/DFS, append all values to a list, and sort using a standard sorting algorithm.O((N1 + N2) log(N1 + N2))
2.Two-Pass Inorder Flatten + Two-Pointer MergeO(N1 + N2)O(N1 + N2)Extract sorted arrays from both BSTs via inorder traversal in O(N1 + N2) time, then merge using two pointers in O(N1 + N2) time.O(N1 + N2)
3.Dual-Stack Streaming Inorder Merge (O(H1 + H2) Space)OptimalO(N1 + N2)O(H1 + H2) stack spaceSimulate inorder traversal on both BSTs simultaneously using two explicit stacks; pop and merge on the fly without storing intermediate arrays.O(N1 + N2)

Common Pitfalls & Crucial Edge Cases

Sorting the whole array

Using O(N log N) sort in an interview when pre-sorted property allows O(N) merge.

Terminating when one stack is empty

Failing to drain the remaining stack leaves elements missing from the result.

Not advancing `c = node.right`

Causes the same node to be pushed infinitely.

Crucial Edge Cases to Validate:

  • One BST is completely empty (`root1 == null`) — Returns inorder of BST2.
  • Both BSTs are empty — Returns empty list [].
  • All elements of BST1 are smaller than all elements of BST2 — Pops entire BST1, then entire BST2.
  • Identical BSTs — Interleaves duplicate keys in sorted pairs.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the two-pointer array merge first, then offer the Dual-Stack Streaming approach for O(H1 + H2) space optimization.
  2. State the space comparison: 'O(N1 + N2) vs O(H1 + H2) memory makes a huge difference on large trees.'
  3. Explain the while-condition c1 || c2 || !s1.empty() || !s2.empty().

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the dual-stack streaming approach use O(H1 + H2) auxiliary space instead of O(N1 + N2)?

2.If BST1 has 10,000 nodes and BST2 has 10,000 nodes, what is the maximum number of elements on both stacks simultaneously if both trees are balanced?

3.Can two BSTs contain duplicate values between them?

Back to DSA Sheet