Create a binary search tree with minimal height from a sorted increasing order array.
If you traverse a Binary Search Tree in inorder traversal, you will get the numbers printed in a sorted increasing order. So you can reverse process and create a binary search tree from a sorted increasing order array of integers.
We will take the middle element and make it the root node. All elements before it should be part of left subtree and all elements after it should be part of the right subtree.
The same process will continue for all subtrees.
TreeNode createBST(int arr, int low, int high)
if( low > high) return null;
int mid = (high - low) + 1;
TreeNode root = new TreeNode();
root.data = arr[mid];
root.left = createBST(arr, low, mid-1);
root.right = createBST(arr, mid+1, high);
Time complexity is O(N)
Space complexity is O(log N)