DEV Community is a community of 788,722 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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: 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
}

That's it !