Skip to content

Instantly share code, notes, and snippets.

@woonketwong
Created January 12, 2014 20:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save woonketwong/8389815 to your computer and use it in GitHub Desktop.
Save woonketwong/8389815 to your computer and use it in GitHub Desktop.
Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height
var createMinimalBST = function(array){
var makeNode = function(value){
var obj = {
value:value,
left:null,
right:null
};
return obj;
};
addToTree = function(array, start, end){
if (end < start){
return null;
}
var median = Math.floor( (start + end) / 2);
var currentNode = makeNode(array[median]);
currentNode.left = addToTree(array, start, median-1);
currentNode.right = addToTree(array, median+1, end);
return currentNode;
};
return addToTree(array, 0, array.length-1);
};
// console.log(createMinimalBST([1,2,3,4,5,6,7,8,9,10]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment