PROBLEM DESCRIPTION
Given a list of integers in sorted order, return the root node of a BST such that the BST has the minimum possible height.
SOLUTION
Since the list of already sorted, we can insert the mid of the list first. The elements to the left will be smaller than the mid element, so they will all go to the left sub tree. Similar for the RST. We can do this recursively by calling the method and passing the sublist.
In this approach, we have used the subList method which has just O(1) time complexity. See: List.subList
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
import java.util.*;
class Program {
public static BST minHeightBst(List<Integer> array) {
if(array.size() == 0)
return null;
int mid = array.size()/2;
BST root = new BST(array.get(mid));
root.left = minHeightBst(array.subList(0,mid));
root.right = minHeightBst(array.subList(mid+1, array.size()));
return root;
}
static class BST {
public int value;
public BST left;
public BST right;
public BST(int value) {
this.value = value;
left = null;
right = null;
}
public void insert(int value) {
if (value < this.value) {
if (left == null) {
left = new BST(value);
} else {
left.insert(value);
}
} else {
if (right == null) {
right = new BST(value);
} else {
right.insert(value);
}
}
}
}
}
Thanks @neha502