StacklessBstIterationInorder.java

    class Node<E> {
      E data;
      Node<E> left;
      Node<E> right;
      Node<E> parent;
      E getData() {return data;}
      Node<E> leftChild() {return this.left;}
      Node<E> rightChild() {return this.right;}
      Node<E> parent() {return this.parent;}

      @Override
      public boolean equals(Object o) {
        if (this == o) { return true; }
        if (o == null || getClass() != o.getClass()) { return false; }
        Node node = (Node) o;
        if (data != null ? !data.equals(node.data) : node.data != null) { return false; }
        return true;
      }

      @Override
      public int hashCode() {
        return data != null ? data.hashCode() : 0;
      }
    }


static <T> void stacklessIterateBSTInOrder(Node<T> root) {
      Node<T> parent = root;
      Node<T> visited = root;
      Node<T> nodePtr = parent;
      
      while (nodePtr != null) {
        //dive deep into left subtree 
        if (nodePtr.leftChild() != null && !visited.equals(nodePtr.leftChild())) {
          nodePtr = nodePtr.leftChild();
          continue;
        }
        //when there's no more left subtree
        System.out.println(nodePtr); //visit current root
        //traverse right subtree
        if (nodePtr.rightChild() != null) {
          nodePtr = nodePtr.rightChild();
        }
        else {
          parent = nodePtr.parent();
          if (parent != null && nodePtr.equals(parent.rightChild())) {
            while (parent != null && nodePtr.equals(parent.rightChild())) {
              nodePtr = parent;
              parent = nodePtr.parent;
            }
          }
          if (parent == null) break; //we've iterated the entire tree
          visited = parent.leftChild();
          nodePtr = parent;
        }
      }
    }