Binary Search tree, inorder method iterative not working

Question

I am currently taking a data structure class in college and we are learning about binary search trees using linked lists. We have gone over the inOrder method recursively but I wanted to try to do the method iteratively. After some research I realized I have to use a stack as i traverse through the tree. I am able to get the the end of the left most side of the tree, however traversing back up the tree is where I am having trouble. I have tried various version of my code but I keep ending up with with a nil pointer exception or it prints out of order.

public void inOrder(){                
    // implement this method using non-recursive solution
   if(m_root==null){
      return;
   }
   Stack<BSTNode> myStack= new Stack<BSTNode>();
   BSTNode current=m_root;
   while (current!= null){
      myStack.push(current);
      current=current.getLeft();
   }
   while (current!=null&& !myStack.isEmpty()){
      current=myStack.peek();
      System.out.print(current.getInfo()+" ");
      myStack.pop();
      if(current.getRight()!=null){
          myStack.push(current);
      }

   }

}

Answer 1

From what I can see there are a few problems with your code in the second while loop. The idea you have is in the right direction however there some logic errors. The conditions you have are correct but should not be together, they should be separated. the code below achieve what you are looking for.

public void inOrder(){                
    // implement this method using non-recursive solution
   if(m_root==null){
      return;
   }
   Stack<BSTNode> myStack= new Stack<BSTNode>();
   BSTNode current=m_root;
   while (current!= null){
      myStack.push(current);
      current=current.getLeft();
   }
   while (!myStack.isEmpty()){
      current=(BSTNode)myStack.pop();
      System.out.print(current.getInfo()+" ");
      if(current.getRight() != null){
         current=current.getRight();
         while (current!= null){
            myStack.push(current);
            current=current.getLeft();
         }
      }
   }

}

Answer 2

For starters, you have in your code two major flaws: you leave the first while loop with current pointing to null and thus you never enter the second while loop. Moreover, I think this

if(current.getRight()!=null){
      myStack.push(current);
  }

should be corrected with myStack.push(current.getRight());, otherwise you're trying to push over and over just the element you popped and you would enter an endless loop. But even so the logic of the exploration is wrong since you'll never go to the left of a node you arrived from a right link. I tried to start from your code and create a working inorder traversal:

public void inOrder(){                

   Stack<BSTNode> myStack= new Stack<BSTNode>();
   Set<BSTNode> visited = new HashSet<BSTNode>();
   BSTNode current = m_root;
   if(current!= null)
       myStack.push(current);
   while (!myStack.isEmpty()){
      current = myStack.peek();
      if(current.getLeft()!= null && !visited.contains(current.getLeft()))
          myStack.push(current.getLeft());
      else{
          //here you explore the parent node
          System.out.print(current.getInfo()+" ");
          visited.add(current);
          myStack.pop();
          //and then you see if it has children on the right
          if(current.getRight()!=null && !visited.contains(current.getRight))
              myStack.push(current.getRight());

      }
   }

}