Problem 🤔

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Input

[-10,-3,0,5,9]

Ouput

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

Real World Applications 🌎

I love this question because it illustrates so clearly the relation between a sorted array and a binary search tree! Once this sinks in hopefully things click :)

The Finer Details 🔎

Let’s look at the following array with unique ints: write algo to create binary search tree with min height

Example 1

Input

[1,2,3,4,5,6,7], len 7, middle 3

Output

1 3 5 7

Example 2

Input

[1,2], len 1, middle 0

By loooking at these examples, one of the first things that stands out is that the root is always the middle of the array! This makes - sense, a min height binary tree will equal (almost) amount of nodes on each side. Therefore, the logical split here is to pick the root as the middle element.

Great, so since this is a recursive problem in nature let’s figure out the base case.

Base case

Array of size 0 or 1? Perfect, all done here!

Array of size 2? We could do this in two ways. Let’s make the larger one the root and the smaller the left child.

Recurrence Relation

Let’s use our recursive function to get the left and right sub tree.

Recursive Solution 💡

Complexity Analysis 🧮

Time complexity

O(n)

One set of constant operations for every node.

Space complexity O(log(n))

Log(n) recurive calls that take the stack space.

Takeaways 🎉🥳

It’s verrrry easy to go from a sorted array to binary search tree and vice versa! The only difference between them is how we choose to represent the data, so don’t be intimidiated!

Resources 📚 💻

Leetcode