Skip to content

Instantly share code, notes, and snippets.

@greim
Last active September 13, 2019 18:08

Revisions

  1. greim renamed this gist Apr 23, 2016. 1 changed file with 0 additions and 0 deletions.
  2. greim created this gist Apr 23, 2016.
    75 changes: 75 additions & 0 deletions ES6 Binary Search Tree Iterable
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,75 @@
    'use strict';

    /*
    * Binary search tree with in-order iteration.
    * http://greim.github.io/gen/dist/00-intro.html
    */

    class Tree {
    add(value) {
    if (this.root) this.root.add(value);
    else this.root = new Node(value);
    }
    has(value) {
    if (this.root) return this.root.has(value);
    else return false;
    }
    delete(value) {
    if (this.root) this.root.delete(value, this, 'root');
    }
    *[Symbol.iterator]() {
    if (this.root) yield* this.root;
    }
    }

    class Node {
    constructor(value) {
    this.value = value;
    }
    add(value) {
    if (value < this.value) {
    if (this.left) this.left.add(value);
    else this.left = new Node(value);
    } else if (value > this.value) {
    if (this.right) this.right.add(value);
    else this.right = new Node(value);
    }
    }
    has(value) {
    if (value < this.value) {
    if (this.left) return this.left.has(value);
    else return false;
    } else if (value > this.value) {
    if (this.right) return this.right.has(value);
    else return false;
    } else if (value === this.value) {
    return true;
    }
    }
    delete(value, parent, which) {
    if (value < this.value) {
    if (this.left) this.left.delete(value, this, 'left');
    } else if (value > this.value) {
    if (this.right) this.right.delete(value, this, 'right');
    } else if (value === this.value) {
    if (this.left) {
    let node = this.left;
    while (node.right) node = node.right;
    this.value = node.value;
    this.left.delete(this.value, this, 'left');
    } else if (this.right) {
    let node = this.right;
    while (node.left) node = node.left;
    this.value = node.value;
    this.right.delete(this.value, this, 'right');
    } else {
    delete parent[which];
    }
    }
    }
    *[Symbol.iterator]() {
    if (this.left) yield* this.left;
    yield this.value;
    if (this.right) yield* this.right;
    }
    }