JavaScript binary search trees with a generator

Before you start

JavaScript classes and recursion.

Insert values, search, and produce the sorted order lazily with a recursive generator.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Because the generator is lazy, a program can stop early. Taking the first three values of a huge tree visits only the leftmost path. If the tree is unbalanced the height approaches n, and every operation degrades to O(n). Balanced variants such as AVL and red–black trees keep the height near log n.

Code example

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

Output

20 30 40 50 60 70 80
true false
height 3
20 30 40

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1class TreeNode {

2 constructor(value) {

3 this.value = value;

4 this.left = null;

5 this.right = null;

6 }

7}

9class Bst {

10 constructor() {

11 this.root = null;

12 }

14 insert(value) {

15 const node = new TreeNode(value);

16 if (this.root === null) {

17 this.root = node;

18 return;

19 }

20 let current = this.root;

21 while (true) {

22 if (value === current.value) {

23 return;

24 }

25 const side = value < current.value ? "left" : "right";

26 if (current[side] === null) {

27 current[side] = node;

28 return;

29 }

30 current = current[side];

31 }

32 }

34 has(value) {

35 let current = this.root;

36 while (current !== null) {

37 if (value === current.value) {

38 return true;

39 }

40 current = value < current.value ? current.left : current.right;

41 }

42 return false;

43 }

45 *inOrder(node = this.root) {

46 if (node === null) {

47 return;

48 }

49 yield* this.inOrder(node.left);

50 yield node.value;

51 yield* this.inOrder(node.right);

52 }

54 height(node = this.root) {

55 return node === null ? 0 : 1 + Math.max(this.height(node.left), this.height(node.right));

56 }

57}

59const tree = new Bst();

60for (const value of [50, 30, 70, 20, 40, 60, 80, 40]) {

61 tree.insert(value);

62}

63console.log([...tree.inOrder()].join(" "));

64console.log(tree.has(60), tree.has(65));

65console.log("height " + tree.height());

67const firstThree = [];

68for (const value of tree.inOrder()) {

69 firstThree.push(value);

70 if (firstThree.length === 3) {

71 break;

72 }

73}

74console.log(firstThree.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
Smaller values go left, larger ones right. The duplicate 40 is ignored earlier.	`—`	—
Attach the new node at the first empty spot on the path.	`—`	—
Delegate to the recursive generator for the left subtree before yielding this node.	`—`	—
In-order traversal gives sorted output.	`—`	20 30 40 50 60 70 80
Search follows one path.	`—`	20 30 40 50 60 70 80 true false
Seven values in a balanced shape have height 3.	`—`	20 30 40 50 60 70 80 true false height 3
Breaking out of the loop stops the generator, so only the leftmost part of the tree is visited.	`—`	20 30 40 50 60 70 80 true false height 3 20 30 40

Behind the scenes

How JavaScript processes this code

A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.

Cost and common mistakes

insert, has: O(h); in-order traversal: O(n) in total, producing values lazily.

Inserting sorted data into a plain BST builds a chain with height n, so operations become O(n).
Deep recursion in the generator can overflow the call stack on a very tall tree.
A Map or Set is better when you do not need ordered traversal. Use a sorted array or a tree library when you do.

Try it yourself

Why use yield* instead of a loop with yield?

Reveal answer and reasoning

yield* delegates to another iterable, here the recursive generator for a subtree, and passes along all its values without a manual loop.