Cormen 10.4.5

walk-tree.js

/**
 * @param {Node} node
 * @template T
 */
function Node (key, left, right) {
  /** @property {T} key */
  this.key = key;
  if (left) left.parent = this;
  if (right) right.parent = this;
  /** @property {Node<T>} left */
  this.left = left || null;
  /** @property {Node<T>} right */
  this.right = right || null;
}
/** @property {Node<T>} parent */
Node.prototype.parent;

/**
 * Walks tree w/o using recursion or allocating extra space
 * @template {T}
 * @param {Node<T>} node
 * @returns {Generator<T>}
 * @usage [...walkTree(tree)]
 */
function* walkTree (node) {
  var prev = null,
      right;
  while (true) {
    if (!node) return;
    if (!prev || prev.parent !== node) {
      yield node.key;
      prev = node;
      node = node.left || node.right || node.parent;
    } else {
      right = node.left === prev ? node.right : null;
      prev = node;
      node = right || node.parent;
    }
  }
}