Recursion

Convert Sorted Array to BST

Given a sorted array arr, convert it to a Binary Search Tree, and return the root. The array may have duplicate values.

You must return a balanced binary tree.

Example:

First Few Test Cases:

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:

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 j==i-1\texttt{j==i-1}.

3. Code

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

Time Complexity O(n)O(n)

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

Mark as Completed:
Submits:
buildBinarySearchTree
Imports:
TreeNode
Test your code to get an output here!
buildBinarySearchTree(
)
Test your code to get an output here!