Converting a Sorted Array to Binary Search Tree in Vanilla Javascript

In my quest to learn data structures and algorithms, I recently came across a leetcode question that I thought was really useful.

The idea is to convert a sorted array to a binary search tree, which is #108, in case you were wondering.

For this question, I decided that using recursion for this one would create an adequate time and space complexity of o(n) for both.

First what you need to do is create an object for a TreeNode(), which if you’re implementing this on leetcode, then this is done for you…

Going through lines 3–7, we start by creating the object with a val, left, and a right. Basically, this says this creates a structure for what each node can have, which is a root value, and a value to the right and left. These left and right values are not required.

Next is to declare some parameters in the sortedArrayToBST function…

What these parameters mean is that we will have an array of nums, a left value set to 0 initially, and a right value being the last value of the array.

Next is to set up an initial condition that if the array is not sorted from low to high then return null.

The next two lines added are going to figure out the middle value and the root. We use the Math.floor() method to get the average of the left value and right value and dividing it by 2.

Then we set the root variable to a new instance of TreeNode with the mid value as the index of the nums array (nums[mid]).

We are using a let instead of a const to make sure that value can change as we recursively change the mid and the root values to fill in the tree.

Next, we will use recursion to call the sortArrayToBST function again and again to input the right and left values until the array is exhausted.

The first function uses the root we created on line 33 and inputs the parameters of the nums array, the left value and the last middle value.

For the right side, we use the nums array again, the mid + 1 value, and the right value.

Here is the completed function with the return of the root.

Here are the results …