[Geeks for Geeks] Merge two BSTs

Merge two BST ‘s

Given two BSTs, return elements of both BSTs in sorted form.

  • Time : O(n + m)
  • Space : O(d)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution
{
public:
//Function to return a list of integers denoting the node
//values of both the BST in a sorted order.
vector<int> merge(Node *root1, Node *root2)
{
vector<Node*> st1, st2;
vector<int> res;
while(root1) {
st1.push_back(root1);
root1 = root1->left;
}
while(root2) {
st2.push_back(root2);
root2 = root2->left;
}
while(!st1.empty() and !st2.empty()) {
auto& mi = (st1.back()->data > st2.back()->data ? st2 : st1);
auto node = mi.back();
mi.pop_back();
res.push_back(node->data);
node = node->right;
while(node) {
mi.push_back(node);
node = node->left;
}
}
auto& st = (st1.empty() ? st2 : st1);
while(!st.empty()) {
auto node = st.back();
st.pop_back();
res.push_back(node->data);
node = node->right;
while(node) {
st.push_back(node);
node = node->left;
}
}

return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/merge-two-bst/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.