0. Problem

We want to write a function that takes in a sorted array, and returns the root node of a BST.

1. Recursion

To build the BST, the very first thing we can do is pick out the root node. Remember, the root node is always the middle element in the array. See below if you need a refresher for why:

Open Spoiler

A BST is a tree such that you'd run Binary Search on it exactly the same way you'd run Binary Search on a sorted array. For example, take this sorted array, and a corresponding BST:

To do a Binary Search, you first start at the middle of the array "12". You then go to the left midpoint "5". Or to the right midpoint "18". You walk in the same directions in both the sorted array and the BST, which is the defining feature of a BST.

Now that we have the root node, we have to build the left and right subtrees. The idea is to use the buildBST function to do this, because we know it always returns a node in the tree. If we can write the buildBST function so that it uses itself, we should have a recursion, and should be able to solve the problem easily.

We can build the left node by using buildBST on the left half of the array. And we can build the right node by using buildBST on the right half of the array.

Here's the recursion, drawn visually:

Here's the recursion written in code:

This recursion is correct, but not optimal. It's bad to do recursion using arrays like this, because it takes time and space to slice them - it creates a whole new array each time.

We can optimize this recursion by instead passing in a starting index i, and a stopping index j in the array (inclusive of both), that tells us how much we've sliced. Using numbers is better than using arrays, because numbers always take O(1) time and space.

2. Base case

The recursion should stop when the array is empty. This happens when $\texttt{j==i-1}$.

3. Code

To code this up, just combine the recursion and base case:

Time Complexity $O(n)$

Space Complexity $O(n)$ for the tree we build, and $O(\log n)$ for the Call Stack.