Binary Tree Traversal - DFS(pre-order, in-order, post-order)

BinaryTreeTraversal.js

class Stack {
  constructor() {
    this.items = Array.prototype.slice.call(arguments, 0);
  }
  push(item) {
    this.items.push(item);
  }
  pop() {
    if (!this.items.length) throw Error('Stack is empty: no items to pop');

    return this.items.pop();
  }
  isEmpty() {
    return !this.items.length;
  }
}

class BinaryTreeNode {
  constructor(data) {
    this.data = data;
    this.leftNode = null;
    this.rightNode = null;
  }
}

class Iterator {
  constructor(list) {
    this.list = list;
    this.cursor = 0;
  }
  first() {
    return this.list[0];
  }
  getNext() {
    return this.list[++this.cursor];
  }
  isDone() {
    return this.cursor === this.list.length - 1;
  }
}

class BinaryTreePreOrderIterator extends Iterator {
  constructor(tree) {
    super();
    this.tree = tree;
    this.list = this.traverse();
  }
  traverse() {
    var result = [];
    if (this.tree.rootNode === null) return result;

    var nodeStack = new Stack();
    nodeStack.push(this.tree.rootNode);

    while(!nodeStack.isEmpty()) {
      var temp = nodeStack.pop();
      result.push(temp.data);
      
      if (temp.rightNode !== null) {
        nodeStack.push(temp.rightNode);
      }
      if (temp.leftNode !== null) {
        nodeStack.push(temp.leftNode);
      }
    }
    return result;
  }
}

class BinaryTreeRecursivePreOrderIterator extends Iterator {
  constructor(tree) {
    super();
    this.tree = tree;
    this.list = this.traverse();
  }
  traverse() {
    return this.traverseCore(this.tree.rootNode, []);
  }
  traverseCore(rootNode, result) {
    if (rootNode !== null) {
      result.push(rootNode.data);
      this.traverseCore(rootNode.leftNode, result);
      this.traverseCore(rootNode.rightNode, result);
    }

    return result;
  }
}

class BinaryTreeInOrderIterator extends Iterator {
  constructor(tree) {
    super();
    this.tree = tree;
    this.list = this.traverse();
  }
  traverse() {
    var result = [];
    var nodeStack = new Stack();
    var currentNode = this.tree.rootNode;
    var isDone = false;

    while (!isDone) {
      if (currentNode !== null) {
        nodeStack.push(currentNode);
        currentNode = currentNode.leftNode;
      } else {
        if (nodeStack.isEmpty()) {
          done = true;
        } else {
          currentNode = nodeStack.pop();
          result.push(currentNode);
          currentNode = currentNode.right;
        }
      }
    }
  }
}

class BinaryTreeRecursiveInOrderIterator extends Iterator {
  constructor(tree) {
    super();
    this.tree = tree;
    this.list = this.traverse();
  }
  traverse() {
    return this.traverseCore(this.rootNode, []);
  }
  traverseCore(rootNode, result) {
    if (rootNode !== null) {
      this.traverseCore(rootNode.leftNode, result);
      result.push(rootNode.data);
      this.traverseCore(rootNode.rightNode, result);
    }

    return result;
  }
}

class BinaryTreeRecursivePostOrderIterator extends Iterator {
  constructor(tree) {
    super();
    this.tree = tree;
    this.list = this.traverse();
  }
  traverse() {
    return this.traverseCore(this.rootNode, []);
  }
  traverseCore(rootNode, result) {
    if (rootNode !== null) {
      this.inOrderTraversalCore(rootNode.leftNode, result);
      this.inOrderTraversalCore(rootNode.rightNode, result);
      result.push(rootNode.data);
    }

    return result;
  }
}

class BinaryTree {
  constructor(rootNode) {
    this.rootNode = rootNode;
  }
  getPreOrderTraversalIterator() {
    return new BinaryTreePreOrderIterator(this);
  }
  getPreOrderRecursiveTraversalIterator() {
    return new BinaryTreeRecursivePreOrderIterator(this);
  }
  getInOrderTraversalIterator() {
    return new BinaryTreeInOrderIterator(this);
  }
  getInOrderRecursiveTraversalIterator() {
    return new BinaryTreeRecursiveInOrderIterator(this);
  }
  getPostOrderTraversalIterator() {
    return new BinaryTreePostOrderIterator(this);
  }
  getPostOrderRecursiveTraversalIterator() {
    return new BinaryTreeRecursivePostOrderIterator(this);
  }
}

var tree = new BinaryTree(new BinaryTreeNode(1));
tree.rootNode.leftNode = new BinaryTreeNode(2);
tree.rootNode.leftNode.leftNode = new BinaryTreeNode(3);
tree.rootNode.leftNode.rightNode = new BinaryTreeNode(4);
tree.rootNode.rightNode = new BinaryTreeNode(5);
tree.rootNode.rightNode.leftNode = new BinaryTreeNode(6);
tree.rootNode.rightNode.rightNode = new BinaryTreeNode(7);
var preOrderTraversalIterator = tree.getPreOrderTraversalIterator();

console.log(preOrderTraversalIterator.first());
while(!preOrderTraversalIterator.isDone()) {
  console.log(preOrderTraversalIterator.getNext());
}