JavaScript binary search trees with a generator
A binary search tree keeps smaller values to the left and larger values to the right. Inserting and searching follow one path from the root, so they take time proportional to the height. A generator can walk the tree in order without building an array: yield* delegates to a recursive call, and the values are produced one at a time, only as fast as the consumer asks.
JavaScript
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class Bst {
constructor() {
this.root = null;
}
insert(value) {
const node = new TreeNode(value);
if (this.root === null) {
this.root = node;
return;
}
let current = this.root;
while (true) {
if (value === current.value) {
return;
}
const side = value < current.value ? "left" : "right";
if (current[side] === null) {
current[side] = node;
return;
}
current = current[side];
}
}
has(value) {
let current = this.root;
while (current !== null) {
if (value === current.value) {
return true;
}
current = value < current.value ? current.left : current.right;
}
return false;
}
*inOrder(node = this.root) {
if (node === null) {
return;
}
yield* this.inOrder(node.left);
yield node.value;
yield* this.inOrder(node.right);
}
height(node = this.root) {
return node === null ? 0 : 1 + Math.max(this.height(node.left), this.height(node.right));
}
}
const tree = new Bst();
for (const value of [50, 30, 70, 20, 40, 60, 80, 40]) {
tree.insert(value);
}
console.log([...tree.inOrder()].join(" "));
console.log(tree.has(60), tree.has(65));
console.log("height " + tree.height());
const firstThree = [];
for (const value of tree.inOrder()) {
firstThree.push(value);
if (firstThree.length === 3) {
break;
}
}
console.log(firstThree.join(" "));