content: package trees;
  
  import java.util.Stack;
  
  public class InOrderTraversal {
  
  
          /*
           * Given a binary tree, write an iterative algorithm to traverse the tree inorder.
           *
           * Binary Node: 100, 50, 200, 25, 75, 125, 350
           * Inorder traversal of the above tree should visit the nodes in the following order:
           * 25, 50, 75, 100, 125, 200, 350
           *
           * Runtime Complexity:
           * Linear, O(n)
           *
           * Memory Complexity:
           * O(h)
           *
           * For an iterative inorder traversal, a stack is used to track the nodes:
           * Step 1: initialize the current_node as root.
           * Step 2: create an empty stack stk.
           * Step 3: Push the current_node in stk and set  current_node = current_node->left until current_node becomes NULL.
           * Step 4:     if stk is not empty and current_node == NULL then
           *                  Print the top element from stk
           *                  Pop the top element from stk and set current_node = element_popped->right
           *                  go to step 3
             Step 5: if current_node is null and stack is empty then algorithm terminates.
           * */
  
      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;
  
  
      protected void inOrderIterative(Node root) {
          if (root == null)
              return;
  
          Stack<Node> stk = new Stack<>();
  
          while (!stk.empty() || root != null) {
              if (root != null) {
                  stk.push(root);
                  root = root.left;
                  continue;
              }
  
              System.out.print(stk.peek().data + " ");
              root = stk.pop().right;
          }
      }
  
  
      public static void main(String[] args) {
          InOrderTraversal inOrderTraversal = new InOrderTraversal();
  
          inOrderTraversal.root1 = new Node(100);
          inOrderTraversal.root1.left = new Node(50);
          inOrderTraversal.root1.right = new Node(200);
          inOrderTraversal.root1.left.left = new Node(25);
          inOrderTraversal.root1.left.right = new Node(75);
          inOrderTraversal.root1.right.left = new Node(125);
          inOrderTraversal.root1.right.right = new Node(350);
  
          inOrderTraversal.inOrderIterative(inOrderTraversal.root1);
          System.out.println();
      }
  }
  