Inorder Tree Traversal algorithm for a Binary Search Tree using Stack

Question

My inputs results 24, 4, 2, 3, 9, 10, 32, and I am getting following result 2, 3, 4, 24.

I am using a stack. When I have manually checked this program the node is not going through else if at 4 on stack, even if has right sub tree.

public void inorderNonRcursive(Node root){

    Stack s = new Stack();
    Node node = root;
    Node k;
    int c=0;

    if(node != null) {
        s.push(node);    
    }

    while(!s.stack.isEmpty()) {   

        //node=(Node) s.stack.get(s.stack.size()-1);
        System.out.println("first condition" + (node.getleft() != null && (node.getVisited() == false)) + "second condi" + (node.getRight() != null));

        if(node.getleft() != null && (node.getVisited() == false)) {
            node = node.getleft();
            s.push(node);
            System.out.println("   from 1           "+(++c)); 

        } else if(node.getRight() != null) {
            k = s.pop();
            System.out.println(k.getvalue());
            node=node.getRight();
            s.push(node);
            System.out.println("    from 2          "+(++c)); 

        } else {
            k = s.pop();
            System.out.println(k.getvalue());
            System.out.println("        from 3      "+(++c)); 
        }  

    }

}

Answer 1

To me, there are two problems in the design:

1. The algorithm seems to be the recursive one adapted for iteration and
2. The Node class knows about being visited.

Here is a different solution (you will need to adapt it a bit):

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

Referring back to my first comments, you don't say you wrote pseudo code and tested it. I think this a key step in writing new algorithms.

Answer 2

This looks like a class exercise, designed to help you understand binary trees.

Before you write any code, draw a picture of your tree, with a value at each node, such as "A", "B", "C", etc. Then starting from the root node, see what you need to do to visit each node in order. Write what you have learned in pseudo code, and test it by doing what it says. Make sure you test all the different cases you can think of for each node (you should have at least three). Put about seven nodes in your tree.

Now you can start on your code. Type in your pseudo code as comments, then insert your Java code in between each comment.

Enjoy :-)