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 !

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

Blog

Converting a sorted array to binary search tree in Javascript

Akhil

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

Binary Search Tree

Join Our Newsletter. No Spam, Only the good stuff.

Related