Generic binary trees

[mateogianolio]

In this short post we will use the new class syntax, and generators to create an incredibly light-weight binary tree representation that can easily be extended into e.g. a heap or a binary search tree (BST).

A binary tree node consists of a value and two children, usually referred to as left and right. To make use of classes, we can represent it as follows:

class BinaryNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Binary tree traversal is usually done with depth-first search. There are three orders of depth-first traversal: pre-order, in-order and post-order.

In-order

1. Traverse the left subtree by recursively calling the in-order function.
2. Display the data part of the root (or current node).
3. Traverse the right subtree by recursively calling the in-order function.

In-order traversal in ES6 generator land looks something like this:

function *traverse(node) {
  if (!node)
    return;

  yield *traverse(node.left);
  yield node.value;
  yield *traverse(node.right);
}

Implementing pre-order and post-order is simply a matter of moving yield node.value before (pre) or after (post) recursion.

We now know enough to start implementing our binary tree.

class BinaryTree {
  *traverse(node) {
    if (node === undefined)
      node = this.root;
    if (!node)
      return;

    yield *this.traverse(node.left);
    yield node.value;
    yield *this.traverse(node.right);
  }
}

Let's create a BST by extending the BinaryTree class with a push method:

class BST extends BinaryTree {
  push(value) {
    var node = new BinaryNode(value);
    if (!this.root) {
      this.root = node;
      return;
    }

    var current = this.root;
    while (current) {
      if (node.value < current.value) {
        if (!current.left) {
          current.left = node;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = node;
          break;
        }
        current = current.right;
      }
    }
  }
}

Tree traversal with the for ... of syntax:

var tree = new BST();
tree.push(8);
tree.push(3);
tree.push(10);
tree.push(1);
tree.push(6);
tree.push(14);
tree.push(4);
tree.push(7);
tree.push(13);

var out = [];
for (var value of tree.traverse())
  out.push(value);

console.log('in-order:', out.join(' '));
// in-order: 1 3 4 6 7 8 10 13 14

We can define a standard iterator ([Symbol.iterator]) for the BinaryTree class to avoid having to call the traverse() function:

[Symbol.iterator]() {
  return this.traverse();
}

Tree traversal looks like this:

var out = [];
for (var value of tree)
  out.push(value);

console.log('in-order:', out.join(' '));
// in-order: 1 3 4 6 7 8 10 13 14

The spread operator can be used to unpack iterables, so the syntax can be further simplified:

console.log('in-order:', ...tree);
// in-order: 1 3 4 6 7 8 10 13 14

Let's finish off by adding a getter for the length property to our BinaryTree class:

get length() {
  return [...this].length;
}

We can now get the length of the tree:

console.log(tree.length);
// 9

[mateogianolio]

Getting tree length (or size, depth, whatever you want to call it) in O(1) is possible if you attach a length property to the class and increment it on push. Otherwise, the general way of getting tree length is:

length(node) {
  if (!node)
    return 0;
  return 1 + this.length(node.left) + this.length(node.right);
}

Getting tree height:

height(node) {
  if (!node)
    return 0;
  return 1 + Math.max(this.height(node.left), this.height(node.right));
}

Link to discussion on reddit.