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

binary-tree, java, stack, tree, tree-traversal

Solution

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;
        }
    }
}

Problem

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`

Original source