Skip to content

Instantly share code, notes, and snippets.

@CarlaTeo
Created May 24, 2021 02:12
Show Gist options
  • Save CarlaTeo/b5ac41c364e5908ab8c0b385306a119e to your computer and use it in GitHub Desktop.
Save CarlaTeo/b5ac41c364e5908ab8c0b385306a119e to your computer and use it in GitHub Desktop.
[JS] Build BST from sorted array
function buildBST(sortedArray) {
if(!sortedArray.length) return null;
if(sortedArray.length === 1) return new Node(sortedArray[0]);
const rootIndex = Math.floor(sortedArray.length / 2);
const root = new Node(sortedArray[rootIndex]);
root.left = buildBST(sortedArray.slice(0, rootIndex));
root.right = buildBST(sortedArray.slice(rootIndex + 1));
return root;
}
// -------------------------------------- Test ------------------------------//
class Node {
constructor(data) {
this.data = data;
this.right = null;
this.left = null;
}
}
const arr = [2,5,6,6,7,8,9,10];
console.log(buildBST(arr));
// Node {
// data: 7,
// right: Node {
// data: 9,
// right: Node { data: 10, right: null, left: null },
// left: Node { data: 8, right: null, left: null }
// },
// left: Node {
// data: 6,
// right: Node { data: 6, right: null, left: null },
// left: Node { data: 5, right: null, left: [Node] }
// }
// }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment