TypeScript generic binary search tree

Order any type with a comparator function and collect the values in sorted order.

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(" "));

Output

20 30 40 50 60 70 80
true false
fig kiwi pear apple

Explanation

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.

Insert and search follow one path from the root, so they take O(h) time for height h. An in-order traversal visits left, node, right and yields the sorted order. The nodes are plain objects with optional left and right children, and null checks are enforced by the compiler when strict null checking is on.

Explore the dry run

Guided walkthroughReady

1type Compare<T> = (a: T, b: T) => number;

3interface TreeNode<T> {

4 value: T;

5 left?: TreeNode<T>;

6 right?: TreeNode<T>;

7}

9class SortedTree<T> {

10 private root?: TreeNode<T>;

11 private compare: Compare<T>;

13 constructor(compare: Compare<T>) {

14 this.compare = compare;

15 }

17 insert(value: T): void {

18 const node: TreeNode<T> = { value };

19 if (!this.root) {

20 this.root = node;

21 return;

22 }

23 let current = this.root;

24 for (;;) {

25 const order = this.compare(value, current.value);

26 if (order === 0) {

27 return;

28 }

29 const side = order < 0 ? "left" : "right";

30 const child = current[side];

31 if (!child) {

32 current[side] = node;

33 return;

34 }

35 current = child;

36 }

37 }

39 has(value: T): boolean {

40 let current = this.root;

41 while (current) {

42 const order = this.compare(value, current.value);

43 if (order === 0) {

44 return true;

45 }

46 current = order < 0 ? current.left : current.right;

47 }

48 return false;

49 }

51 toArray(): T[] {

52 const out: T[] = [];

53 const walk = (node?: TreeNode<T>): void => {

54 if (!node) return;

55 walk(node.left);

56 out.push(node.value);

57 walk(node.right);

58 };

59 walk(this.root);

60 return out;

61 }

62}

64const numbers = new SortedTree<number>((a, b) => a - b);

65[50, 30, 70, 20, 40, 60, 80, 40].forEach((n) => numbers.insert(n));

66console.log(numbers.toArray().join(" "));

67console.log(numbers.has(60), numbers.has(65));

69const byLength = new SortedTree<string>((a, b) => a.length - b.length || a.localeCompare(b));

70["pear", "fig", "apple", "kiwi", "fig"].forEach((w) => byLength.insert(w));

71console.log(byLength.toArray().join(" "));

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The tree gets its ordering from a function, so it works with any type.	`—`	—
Negative means go left, positive means go right, zero means the value is already there.	`—`	—
Attach the new node at the first empty child on the path.	`—`	—
In-order traversal gives sorted numbers. The duplicate 40 was ignored.	`—`	20 30 40 50 60 70 80
Search follows one path.	`—`	20 30 40 50 60 70 80 true false
Strings ordered by length, then alphabetically. The second fig is a duplicate and is ignored.	`—`	20 30 40 50 60 70 80 true false fig kiwi pear apple

Cost and common mistakes

insert and has are O(h); toArray is O(n).

A comparator must be consistent. If compare(a, b) and compare(b, a) disagree, the tree can lose values.
A plain BST degrades to O(n) on sorted input. Use a self-balancing tree for guaranteed O(log n).
Two values that compare as equal are treated as duplicates here, even if they are different objects.

Try it yourself

How would you sort people by age with this tree?

Reveal answer and reasoning

Create new SortedTree<Person>((a, b) => a.age - b.age). People with equal ages would count as duplicates, so break ties with another field if needed.

TypeScript generic binary search tree

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading