Convert a Sorted Array into a Binary Search Tree

Given a sorted array, convert it into a binary search tree.

The intuition behind this problem is to recognize that the midpoint of the current range is used to construct the current node. The left child node will be constructed with the midpoint of the left half of the current range. Similarly, the right child node will be constructed using the midpoint of the right half of the current range.

We can use the divide-and-conquer technique in solving this problem. At each iteration, we instantiate a new node with the value of the midpoint of the current range. This is recursively applied to the left half and the right half to construct the left and right child, respectively. One important thing to keep in mind is that the range will change with each iteration.

const toBinarySearchTree = (arr) => {
  return toBinarySearchTree(arr, 0, arr.length - 1);
}

const toBinarySearchTree = (arr, l, r) => {
  if (r < l) return null;

  const m = (l + r) / 2;
  const cur = new BinarySearchTreeNode(arr[m]);

  cur.left = toBinarySearchTree(arr, l, mid - 1);
  cur.right = toBinarySearchTree(arr, m + 1, r);
  return cur;
}

The time complexity for this problem is O(n) because we need to do processing for each element of the array. The space complexity for this problem is O(log(n)) because the problem yield a balanced tree where the recursive call stack will be as deep as the height of the tree.