DEV Community

Akhil
Akhil

Posted on

Converting a sorted array to binary search tree in Javascript

Question: given a sorted array, convert it to a binary search tree.

Let's start by understanding what's a binary search tree is?

Binary Search Tree

A binary search tree is a type of tree in which at any root, the elements in it's left subtree are strictly decreasing and elements in it's right subtree are strictly increasing.

So we've to figure out a way to choose elements from array such that the binary search tree constraints are followed.

This leads to an intuition of picking element at the middle index of a subarray.

Let's understand this:

Alt Text

so based on this let's write our solution:


var sortedArrayToBST = function(nums) {
    return traverse(nums,0,nums.length-1); // recursively parse through array
};

function traverse(nums,start,end){
    if(start>end){                        // if start>end means left tree or right subtree is not possible so return null
        return null;
    }
    let mid = Math.floor((start+end)/2);       // get the mid index
    let root = new TreeNode(nums[mid]);        // make a new node
    root.left = traverse(nums,start,mid-1);    // now recursively generate left subtree
    root.right = traverse(nums,mid+1,end);     // similarly generate right subtree
    return root;                               // return the root
}

Enter fullscreen mode Exit fullscreen mode

That's it !

github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/convertSortedArrayToBST.js

Top comments (2)

Collapse
 
darkmg73 profile image
DarkMG73

Hello. I see you are using a class TreeNode, but do not create that class anywhere in your code. Am I missing something?

Collapse
 
jayparkongithub profile image
Jay Park • Edited

I assume this problem is pulled directly from Leetcode, which has a built-in class for TreeNode. I put the class down below if you're interested.

/**
 * 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)
 * }
 */
/**
Enter fullscreen mode Exit fullscreen mode