Sorted Array to Binary Search Tree in Javascript

This post will be going over a solution in javascript for Leetcode problem 108. Convert Sorted Array to Binary Search Tree.

In this problem we’re given a sorted array, and with it are asked to build a height-balanced binary search tree.

To start, we need to refresh on some definitions:

A binary search tree is a binary tree (i.e. a tree where each parent node has 0–2 children), whose nodes meet the following criteria (source: https://www.geeksforgeeks.org/binary-search-tree-data-structure/):

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

A height balanced tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

This problem also implements its binary tree as follows:

Definition for a binary tree node:
   function TreeNode(val, left, right) {
   this.val = (val===undefined ? 0 : val)
   this.left = (left===undefined ? null : left)
   this.right = (right===undefined ? null : right)
   }

So in other words, if we were to create a new node with a value of 2 we could simply do

node = new TreeNode(2) 

and then set node.left and node.right accordingly.

If you are implementing your nodes differently you can tweak this solution, however at a high level the logic will be the same.

When I was first approaching this problem, I got caught up on how to ensure the tree was height balanced. With the following solution, this will happen naturally as we recursively build our tree.

When thinking about how to build our tree recursively, it can get a little confusing trying to visualize every call of the recursive function. Instead, let’s start by asking what we want to do at our root node (which we will then repeat iteratively for the rest of the tree).

To build our construct tree helper function, we will give it 3 arguments: our nums array, the left bound of the section at which we are currently looking, and the right bound of the section at which we are currently looking.

This will allow us to get the midpoint of the array, which will be our root node.

We then need to assign the current root node’s children by assigning this.left and this.right.

Let’s take the following array as an example:

Input: nums = [-10,-3,0,5,9]

If we know that for each node, the value of the left node must be less than the value of the current node, we can see that our root would need to be the middle value in the array.

So once we have gotten the middle value in the array (which in the above would be 0), we need to create a new node with that value.

We know that the BST rules are true for every subtree of our BST, so once we have the overall root of the tree, we can complete this same process for the left and right subtrees. All we need to do is call the function recursively 1) for the left subtree and 2) for the right subtree.

We do this by simply shifting the bounds we are passing in as arguments to our recursive function. For our left subtree, this means the left bound will stay as the leftmost (smallest) value in the sorted array, and the right bound will be the node to the left of our current midpoint. Similarly the for the right subtree, our right node will be the rightmost (largest) value in the array, and the left bound will become the value to the right of our midpoint.

We then repeat the process of finding the middle nodes of those subtrees and assigning their children recursively.

After that, we simply need to add our base case and return value. For both our left and right subtrees we are keeping one pointer in place, and moving the other pointer to the left or to the right. Therefore, when the pointers reach the end of the array, the pointers will eventually meet / become equal. This will be our base case for which we will return null, and the nodes at the end of our recursion will become the leaves of our tree.

Within our recursive function we will then just return the original root node, which will have the connections we’ve established recursively to all its children.

Here is the code for the solution written out:

Hope this helps!