class BinaryTreePostOrder {

  public List<BinaryNode> getIterative(BinaryNode root) {
    validateTree(root);
    List<BinaryNode> result = new LinkedList<BinaryNode>();
    Stack<BinaryNode> stack = new Stack<BinaryNode>();
    stack.push(root);

    BinaryNode prev = null;
    while (!stack.empty()) {
      BinaryNode current = stack.peek();

      //Go down the tree. check if current node is leaf, if so, process it and pop stack, otherwise,
      //keep going down
      if (prev == null || prev.getLeft() == current || prev.getRight() == current) {
        //prev == null is the situation for the root node
        if (current.getLeft() != null) {
          stack.push(current.getLeft());
        } else if (current.getRight() != null) {
          stack.push(current.getRight());
        } else {
          stack.pop();
          result.add(current);
        }

        //Go up the tree from left node need to check if there is a right child
        //if yes, push it to stack otherwise, process parent and pop stack
      } else if (current.getLeft() == prev) {
        if (current.getRight() != null) {
          stack.push(current.getRight());
        } else {
          stack.pop();
          result.add(current);
        }

        //Go up the tree from right node after coming back from right node, process parent node
        //and pop stack.
      } else if (current.getRight() == prev) {
        stack.pop();
        result.add(current);
      }

      prev = current;
    }
    return result;
  }

}