Stack tree traversal algorithm for binary search tree using stack

Question

My input results are 24, 4, 2, 3, 9, 10, 32 , and I get the following result 2, 3, 4, 24 .

I am using the stack. When I manually checked this program, node does not go through else if in 4 on the stack, even if it has the correct subtree.

 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

For me, there are two problems in design:

• The algorithm appears to be recursive, adapted for iteration, and
• The Node class knows about the visit.

Here is another solution (you 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; } } } 

Returning to my first comments, you are not saying that you wrote the pseudocode and tested it. I think this is a key step in writing new algorithms.

Answer 2

It looks like a class exercise designed to understand binary trees.

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

Now you can start with the code. Enter your pseudocode as comments, then paste the Java code between the comments.

Enjoy :-)