TypeScript generic binary search tree
A generic binary search tree needs a way to order its elements. Instead of requiring the element type to be comparable, the tree takes a comparator function (a, b) => number that returns a negative number, zero, or a positive number. This is the same convention as Array.prototype.sort and lets one tree class order numbers, strings, or records by any field.
TypeScript
type Compare<T> = (a: T, b: T) => number;
interface TreeNode<T> {
value: T;
left?: TreeNode<T>;
right?: TreeNode<T>;
}
class SortedTree<T> {
private root?: TreeNode<T>;
private compare: Compare<T>;
constructor(compare: Compare<T>) {
this.compare = compare;
}
insert(value: T): void {
const node: TreeNode<T> = { value };
if (!this.root) {
this.root = node;
return;
}
let current = this.root;
for (;;) {
const order = this.compare(value, current.value);
if (order === 0) {
return;
}
const side = order < 0 ? "left" : "right";
const child = current[side];
if (!child) {
current[side] = node;
return;
}
current = child;
}
}
has(value: T): boolean {
let current = this.root;
while (current) {
const order = this.compare(value, current.value);
if (order === 0) {
return true;
}
current = order < 0 ? current.left : current.right;
}
return false;
}
toArray(): T[] {
const out: T[] = [];
const walk = (node?: TreeNode<T>): void => {
if (!node) return;
walk(node.left);
out.push(node.value);
walk(node.right);
};
walk(this.root);
return out;
}
}
const numbers = new SortedTree<number>((a, b) => a - b);
[50, 30, 70, 20, 40, 60, 80, 40].forEach((n) => numbers.insert(n));
console.log(numbers.toArray().join(" "));
console.log(numbers.has(60), numbers.has(65));
const byLength = new SortedTree<string>((a, b) => a.length - b.length || a.localeCompare(b));
["pear", "fig", "apple", "kiwi", "fig"].forEach((w) => byLength.insert(w));
console.log(byLength.toArray().join(" "));