README.md

Iterable Binary Search Tree

Iterators are so useful, that it has now become one of JavaScript's core features. Generators were devised in order to facilitate the creation of iterators. Better yet, with generators, you can nest iterators, and yield a "flattened" result.

The binary search tree is a classic example of where "nested" iterators will be useful.

Usage

const BinarySearchTree = require('./bst.js');

const tree = new BinarySearchTree();

tree.insert(3, 'foo');
tree.insert(10, 'bar');
tree.insert(21, 'baz');
tree.insert(13, 'widgets');
tree.insert(12, 'foobar');

console.log([...tree]);

bst.js

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insert(key, value) {
    if (this.key === key) { this.value = value; return; }
    if (key < this.key) {
      if (this.left === null) {
        this.left = new Node(key, value);
      } else {
        this.left.insert(key, value);
      }
    } else if (key > this.key) {
      if (this.right === null) {
        this.right = new Node(key, value);
      } else {
        this.right.insert(key, value);
      }
    }
  }

  search(key) {
    if (this.key === key) {
      return value;
    }
    if (key < this.key) {
      if (this.left === null) { return null; }
      return this.left.search(key);
    } else if (key > this.key) {
      if (this.right === null) { return null; }
      return this.right.search(key);
    }
  }

  *[Symbol.iterator]() {
    if (this.left !== null) { yield * this.left; }
    yield this.value;
    if (this.right !== null) { yield * this.right; }
  }
}

module.exports = class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(key, value) {
    if (this.root === null) { this.root = new Node(key, value); }
    else { this.root.insert(key, value); }
  }

  search(key) {
    if (this.root !== null) { return this.root.search(key); }
  }

  *[Symbol.iterator]() {
    if (this.root !== null) { yield * this.root; }
  }
};