Now that we understand how balancing works, we can do the fun part, which is coding. We can start the algorithm by creating the array from BST, and calling build function, giving it the starting (0
) and ending (n-1
) of the array. The full code is given below.
xxxxxxxxxx
28
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
​
function arrayToBST(arr) {
if (!arr.length) return null;
let mid = Math.floor(arr.length / 2);
let root = new Node(arr[mid]);
root.left = arrayToBST(arr.slice(0,mid));
root.right = arrayToBST(arr.slice(mid+1));
return root;
}
​
function preOrder(node) {
if (node) {
console.log(node.data);
preOrder(node.left);
preOrder(node.right);
}
}
​
let arr = [10, 11, 17, 19, 30, 31, 37, 38];
let root = arrayToBST(arr);
preOrder(root);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment