0. Problem

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

buildBST(arr)

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 SpoilerClose 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:

buildBST(arr) = (
    mid = len(arr)//2

    root = TreeNode(arr[mid]) # build root
    root.left = buildBST(arr[:mid]) # build left node
    root.right = buildBST(arr[mid+1:]) # build right node

    return root
)

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.

# builds BST of arr[i,...,j]
buildBST(i, j) = (
    mid = (i + j)//2

    root = TreeNode(arr[mid]) # the root node has the middle element 
    root.left = buildBST(i, mid-1) # build children using left and right halves
    root.right = buildBST(mid+1, j)
    
    return root
)

2. Base case

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

if j == i-1:
    return None

3. Code

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

def buildBinarySearchTree(arr):

    def buildBST(i, j):
        # base case
        if j == i-1:
            return None

        # recursion
        mid = (i + j)//2

        root = TreeNode(arr[mid])
        root.left = buildBST(i, mid-1)
        root.right = buildBST(mid+1, j)

        return root

    # build BST for entire array
    return buildBST(0, len(arr)-1)

Time Complexity $O(n)$

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