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 !
Top comments (2)
Hello. I see you are using a class TreeNode, but do not create that class anywhere in your code. Am I missing something?
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.