Problem Statement

Create a binary search tree with minimal height from a sorted increasing order array. 

Approach

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.

Solution

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);

 

  return root;

}

Complexity

Time complexity is O(N)

Space complexity is O(log N)