I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.
I was thinking especially about the node insertion method. Here's my implementation:
class BinaryTree {
// ... initialization
add(val) {
if(this.root === null) {
this.root = new Node(val);
return ;
}
this.addNode(val, this.root);
}
addNode(val, node) {
if(!!!this.comparator) throw new Error('this.comparator cannot be undefined.');
let comp = this.comparator(val, node.val);
if(comp === -1) {
if(node.left === null) {
node.left = new Node(val);
return ;
}
this.addNode(val, node.left);
}
else if(comp === 1) {
if(node.right === null) {
node.right = new Node(val);
return ;
}
this.addNode(val, node.right);
}
}
// ... other methods
}
where this.comparator = (v1, v2) => { return (v1 <= v2) ? -1 : 1; };
My questions are:
- Is there a way to modify this
add
method such that it can balance the tree after every addition? - If so, by factor would the time complexity of
add
be growing?