Fixing my implementation of "inorder tree traversal" algorithm with a Stack

Question

Part of it is that I have to implement a non-recursive method of a inorder traversal of a binary tree. I am kind of stuck. Here is what I have so far:

public void inorder(BinaryTree v) {
    Stack<BinaryTree> stack = new Stack<BinaryTree>();
    stack.push(v);
    System.out.println(v.getValue());

    while(!stack.isEmpty()) {
        while(v.getLeft() != null) {
            v = v.getLeft();
            stack.push(v);
            System.out.println(v.getValue());
        }

        while(v.getRight() != null) {
            v = v.getRight();
            stack.push(v);
            System.out.println(v.getValue());
        }
                stack.pop();
    }
}

I noticed that it only prints out the left side of my tree, e.g.

          A
        /   \
       B     C
     /   \  /  \
    D     E F   G
   /  \
  H     I
 / \
J   K

Gives A B D H J

Answer 1

You can greatly simplify the above with a single while loop:

Stack<Node> stack = new Stack<>();
Node current = root;
while(current != null || !stack.isEmpty()){
  if(current != null){
    stack.push(current);
    current = current.left;
  } else if(!stack.isEmpty()) {
    current = stack.pop();
    process(current);
    current = current.right;
  }
}

Basically the code above pushes left branches on the stack until it reaches the leftmost node in the branch. Then it pops it and processes it (you can print it or do something else with it) and then it pushes the right branch on the stack to process since the left branch and the node itself are done.

Answer 2

Following your code, the while loop for the getLeft() part goes all the way down the left of the tree, then exits. v is now node J, which has no right child so the next while loop doesn't run.

Try this code example: http://www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflow answer: https://stackoverflow.com/a/12718147/1178781

// Inorder traversal:
// Keep the nodes in the path that are waiting to be visited
Stack s = new Stack(); 
// The first node to be visited is the leftmost
Node node = root;
while (node != null) {
    s.push(node);
    node = node.left;
}
// Traverse the tree
while (s.size() > 0) {
    // Visit the top node
    node = (Node)s.pop();
    System.out.println((String)node.data);
    // Find the next node
    if (node.right != null) {
        node = node.right;
        // The next node to be visited is the leftmost
        while (node != null) {
            s.push(node);
            node = node.left;
        }
    }
}