How to solve LeetCode’s “Convert Sorted Array to Binary Search Tree” problem with Javascript

Previously, we covered the basics of binary search trees. Yes, they can seem really scary at first. But now that we’ve gotten to know them, it’s time to step out into the forest, flex our tree-climbing 💪 with Javascript, and solve an actual BST problem!

Here’s the BST algorithm problem from LeetCode which we’ll tackle with Javascript today:

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.

🛑🤚 Before you move on, try to apply what we’ve learned about binary search trees, and give it a try on your own!

Ready? Here’s my approach:

Step 0: Take a deep breath 🤓

Step 1: Assess what we know

• Input: our input will be a SORTED array, with elements in ascending order.
• Output: a binary search tree (meaning that all nodes / subtrees to the left of any given node should have a value which is less than the current value, and to the right should be greater than). Our function should return the top-most root node of the entire tree.
• Output constraint: the tree should be “height-balanced”. It basically means that both branches from any given node should have close to the same height (they never differ by more than one level).

• We are free to use a pre-defined function that LeetCode provides for us, called TreeNode. When we call it with the new keyword and pass it a value as an argument (let’s say for example, 8), it returns a new node, which is just an object with three properties (val, left, right). Here is the creation of a new node in action:

Step 2: Draw some sample inputs and expected outputs

I always find that it helps to write out lots of different cases for inputs / expected outputs. Make sure to test out all kinds of inputs (odd vs. even length inputs, inputs that are long vs short, inputs that are weird such as an empty array or arrays with only one item).

Step 3: Pseudocode our approach

Now we’re ready to pseudocode! Here’s my general thought process for how our function will work:

1. Find the center element of the array and make it the root node. Why? This will encourage our tree to be height-balanced, since everything to the left of our center represents the left subtree, and everything to the right of our center represents the right subtree. If there isn’t an exact center element, then round up to the next element on the right.
2. Define .left | we know that the left sub-array (from index 0 up until and not including the center) represents the LEFT SUBTREE of our current node. So set .left equal to the result of calling this function again, but this time pass in our left sub-array (which represents the left sub-tree) as the argument.
3. Define .right | same thing we did above for the left, but now on the right sub-array (from index right after the center up until and including the last index)
4. Return the root. FYI, when we reach this point recursively (anywhere deeper than 1 level in the call stack), it will return the current root node to its calling execution context (a.k.a. the node above it in the tree) to set it as the value of either .left or .right!
5. Base Case #1: We’ve hit a leaf at the bottom of the tree! How do we know that? We hit this case when the array fed into our function has a length of 1. This means that there are no remaining child nodes or subtrees to either the left or the right, so now we can just return this as a plain old node. After we return, our program will recurse back up the tree and pop this execution context off the top of the call stack.
6. Base Case #2: We’ve hit a node that doesn’t exist! How do we know we’ve hit a non existent node? We hit this case when the array fed into our function has a length of 0. So now we can just return null. After we return, our program will recurse back up the tree and pop this execution context off the top of the call stack.
7. Move our base case logic up to the top of our function, since we want to account for these scenarios first before going through any of the other logic.

Here’s a whiteboard representation of what our function is doing for sample input [-20, -10, -3, 0, 5, 9, 27]:

And below is another example for sample input [-10, -3, 0, 5, 9]. Remember, if there’s not an exact center, we round up (to the element on the right):

Step 4: Code!

Finally, we are ready to actually write code! It may be tempting to jump straight here, but it’s really important to first do the steps above so that we can wrap our head around the problem. And now (🥁 roll please)… here is the solution in Javascript:

This is only one way of doing this problem — feel free to take it further and try to optimize it!

Takeaways:

Binary search trees don’t have to be scary! They can actually be fun once we get to know their characteristics. Personally, I now get excited when I come across a binary search tree problem as I do my software engineering interview prep (rather than roll on the floor in defeat 😭 which is kind of what happened when I first encountered them). BSTs are powerful data structures, and now we have them as our friends! Keep climbing and coding 👍

Props to:

Leaf It Up To Binary Trees, Vaidehi Joshi

Implementation of Binary Search Tree in Javascript, Geeks for Geeks

How to Solve a Binary Search Tree Problem, Rachel Lum

Tree (data structure), Wikipedia

Learn and Understand Recursion in Javascript, Brandon Morelli

Javascript Coders Meetup