PROBLEM DESCRIPTION
Given two BSTs, return elements of merged BSTs in sorted form.
SOLUTION
We can solve this by performing inorder traversals on both binary search trees to get sorted lists, then merging them using a two-pointer technique to create a single sorted list efficiently.
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
44
45
46
47
48
49
50
class Solution {
public List<Integer> merge(Node root1, Node root2) {
// Perform inorder traversal on both trees and merge the sorted lists
return mergerSortedLists(inorder(root1, new ArrayList<>()), inorder(root2, new ArrayList<>()));
}
// Merges two sorted lists into one sorted list
public List<Integer> mergerSortedLists(List<Integer> list1, List<Integer> list2){
int i = 0;
int j = 0;
List<Integer> list = new ArrayList<>();
while(i < list1.size() && j < list2.size()){
if(list1.get(i) < list2.get(j)){
list.add(list1.get(i));
i++;
} else {
list.add(list2.get(j));
j++;
}
}
while(i < list1.size()){
list.add(list1.get(i));
i++;
}
while(j < list2.size()){
list.add(list2.get(j));
j++;
}
return list;
}
public List<Integer> inorder(Node root, List<Integer> list){
if(root == null)
return list;
inorder(root.left, list);
list.add(root.data);
inorder(root.right, list);
return list;
}
}