Problem
Given an ordered integer array, build a binary search tree from it.
For example, given an array {1, 3, 6, 8, 9, 10}, the output should be a binary search tree rooted at 6 as follows:
6
3 9
1 8 10
Solution
The array is ordered, so we can find the middle point, which corresponds to the root of a subtree. The middle point divide the array into the left and right. We use the left subarray to build the left subtree and the right subarray to build the right subtree. We can do this recursively. The exit condition is, the subarray size is 1, then we create a new node with the value and return the node.
class ArrayToBst {
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static void main(String...args) {
int[] arr = new int[] {1, 3, 6, 8, 9, 10};
buildTree(arr);
}
public static void buildTree(int[] arr) {
Node root = buildTree(arr, 0, arr.length - 1); //0, 5
printTree(root);
}
private static void printTree(Node root) {
if(root == null) return;
printTree(root.left);
System.out.print(root.value + " ");
printTree(root.right);
}
private static Node buildTree(int[] arr, int lo, int hi) { //0 5; 3 5; 5 5
if(lo > hi) {
return null;
}
int mid = lo + (hi - lo)/2; //0 + (5 - 0)/2 = 2; 3 + 1 = 4; 5
Node root = new Node(mid, null, null);
root.value = arr[mid];
root.left = buildTree(arr, lo, mid - 1); // 5, 4
root.right = buildTree(arr, mid + 1, hi); //3, 5; 6, 5
return root;
}
}
Iterate the array cost N, insert in BST in worst case cost N, but in average cost logN, so the time complexity is O(N), the space complexity is O(N).
