binary-tree-node.js

const LEFT = Symbol('left');
const RIGHT = Symbol('right');

// tag::snippet[]
/**
 * Binary Tree Node
 *
 */
class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.meta = {};
    // end::snippet[]
    this.parent = null;
    this.parentSide = null;
  }

  // tag::setAndUpdateParent[]
  /**
   * Set a left node descendants.
   * Also, children get associated to parent.
   */
  setLeftAndUpdateParent(node) {
    this.left = node;
    if (node) {
      node.parent = this;
      node.parentSide = LEFT;
    }
  }

  /**
   * Set a right node descendants.
   * Also, children get associated to parent.
   */
  setRightAndUpdateParent(node) {
    this.right = node;
    if (node) {
      node.parent = this;
      node.parentSide = RIGHT;
    }
  }
  // end::setAndUpdateParent[]

  /**
   * Tell if is parent's left or right child
   *
   * @returns {string} side (left or right) this node is of its parent
   */
  get parentChildSide() {
    if (this.parent) {
      return this.isParentLeftChild ? 'left' : 'right';
    }

    return 'root';
  }

  /**
   * Return true if this node is its parent left child
   */
  get isParentLeftChild() {
    return this.parentSide === LEFT;
  }

  /**
   * Return true if this node is its parent right child
   */
  get isParentRightChild() {
    return this.parentSide === RIGHT;
  }

  /**
   * Node is leaf is it has no descendants
   */
  get isLeaf() {
    return !this.left && !this.right;
  }

  /**
   * Get sibling of current node
   */
  get sibling() {
    const { parent } = this;
    if (!parent) return null;
    return parent.right === this ? parent.left : parent.right;
  }

  /**
   * Get parent sibling = uncle (duh)
   */
  get uncle() {
    const { parent } = this;
    if (!parent) return null;
    return parent.sibling;
  }

  get grandparent() {
    const { parent } = this;
    return parent && parent.parent;
  }

  /**
   * Get color
   */
  get color() {
    return this.meta.color;
  }

  /**
   * Set Color
   */
  set color(value) {
    this.meta.color = value;
  }

  // tag::avl[]
  /**
   * @returns {Number} left subtree height or 0 if no left child
   */
  get leftSubtreeHeight() {
    return this.left ? this.left.height + 1 : 0;
  }

  /**
   * @returns {Number} right subtree height or 0 if no right child
   */
  get rightSubtreeHeight() {
    return this.right ? this.right.height + 1 : 0;
  }

  /**
   * Get the max height of the subtrees.
   *
   * It recursively goes into each children calculating the height
   *
   * Height: distance from the deepest leaf to this node
   */
  get height() {
    return Math.max(this.leftSubtreeHeight, this.rightSubtreeHeight);
  }

  /**
   * Returns the difference the heights on the left and right subtrees
   */
  get balanceFactor() {
    return this.leftSubtreeHeight - this.rightSubtreeHeight;
  }
  // end::avl[]

  /**
   * Serialize node's values
   */
  toValues() {
    return {
      value: this.value,
      left: this.left && this.left.value,
      right: this.right && this.right.value,
      parent: this.parent && this.parent.value,
      parentSide: this.parentSide,
    };
  }

  /**
   * Get and Set data value
   * @param {any} value (optional) if not provided is a getter, otherwise a setter.
   */
  data(value) {
    if (value === undefined) {
      return this.meta.data;
    }
    this.meta.data = value;
    return this;
  }

  /**
   * Convert Binary tree from an iterable (e.g. array)
   * @param {array|string} iterable - The iterable
   */
  static from(iterable = []) {
    const toBinaryTree = (array, index = 0) => {
      if (index >= array.length) return null;
      const node = new BinaryTreeNode(array[index]);
      node.setLeftAndUpdateParent(toBinaryTree(array, index * 2 + 1));
      node.setRightAndUpdateParent(toBinaryTree(array, index * 2 + 2));
      return node;
    };
    return toBinaryTree(Array.from(iterable));
  }
}

BinaryTreeNode.RIGHT = RIGHT;
BinaryTreeNode.LEFT = LEFT;

module.exports = BinaryTreeNode;