content: package trees;
  
  import java.util.Stack;
  
  public class BinaryTreeIterator {
  
  
      /*
       * Implement a class that implements an InOrder Iterator on a Binary Tree
       *
       * */
  
      private static class Node {
          private int data;
          private Node left, right;
  
          Node(int item) {
              data = item;
              left = right = null;
          }
  
          public int getData() {
              return data;
          }
  
          public Node getLeft() {
              return left;
          }
  
          public Node getRight() {
              return right;
          }
      }
  
  
      private Node root1;
  
      private class InOrderTreeIterator {
          private Stack<Node> stk = new Stack();
  
          public InOrderTreeIterator(Node root) {
              while (root != null) {
                  stk.push(root);
                  root = root.left;
              }
          }
  
  
          public boolean hasNext() {
              return !stk.isEmpty();
          }
  
          public Node getNext() {
              if (stk.isEmpty())
                  return null;
  
              Node rVal = stk.pop();
              Node temp = rVal.right;
              while (temp != null) {
                  stk.push(temp);
                  temp = temp.left;
              }
              return rVal;
          }
      }
  
      public void inOrderUsingIterator(Node root) {
          InOrderTreeIterator iterator = new InOrderTreeIterator(root);
          while (iterator.hasNext()) {
              System.out.print(iterator.getNext().data + ", ");
          }
          System.out.println();
      }
  
  
      public static void main(String[] args) {
  
          BinaryTreeIterator tree = new BinaryTreeIterator();
          tree.root1 = new Node(100);
          tree.root1.left = new Node(50);
          tree.root1.right = new Node(200);
          tree.root1.left.left = new Node(25);
          tree.root1.left.right = new Node(75);
          tree.root1.right.left = new Node(125);
          tree.root1.right.right = new Node(350);
  
          tree.inOrderUsingIterator(tree.root1);
          System.out.println();
      }
  }
  