Fixing my implementation of the tree walk algorithm using Stack

Question

Part of this is that I have to implement a non-recursive method of traversing an object in a binary tree. I'm kinda stuck. Here is what I still have:

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 the left side of my tree, for example

  A / \ BC / \ / \ DEFG / \ HI / \ JK 

Gives ABDHJ

Answer 1

Following your code, the while loop for the getLeft() goes down the left getLeft() tree, and then ends. v now a J node that does not have a right child, so the next while loop does not start.

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

StackOverflow answer: fooobar.com/questions/1468870 / ...

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

Answer 2

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 the left branches onto the stack until it reaches the leftmost node in the branch. Then it pushes it and processes it (you can print it or do something else with it), and then it pushes the right branch onto the stack for processing, since the left branch and node itself are done.

Answer 3

I have a solution that uses only one while loop. This is similar to Giovanni's decision, but in my opinion, it looks cleaner and more readable. In particular, the design is similar to a recursive solution for In Order Traversal, which facilitates understanding.

 public void InOrderTraversal(Node root) { if (root == null) return; Deque<Node> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { Node curr = stack.peek(); if (curr.left != null) { stack.push(curr.left); continue; } Node node_to_print = stack.pop(); System.out.println(node_to_print.data); if (curr.right != null) { stack.push(curr.right); } } return; } 

Note. I used the Deque interface to implement my stack. According to the API, this should be the preferred method: http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

Answer 4

Another simple binary workaround implementation:

 import java.util.Stack; public class BinaryTree { public static void main(String args[]) { Node root = Node.createDummyTree(); Node tnode; //= root; Stack<Node> stack = new Stack<Node>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { tnode = stack.pop(); if (tnode != null) { System.out.println(tnode.value); if(tnode.rightNode != null) { stack.push(tnode.rightNode); } if (tnode.leftNode != null) { stack.push(tnode.leftNode); } } } } } class Node { public Node leftNode; public Node rightNode; public String value; Node(String value) { this.value = value; } /** * Construct a dummy binary Tree * A * / \ * BC * / \ / \ * DEFG * / \ / \ / \ / \ * HIJKLMNO * @return */ public static Node createDummyTree(){ Node root = new Node("A"); root.leftNode = new Node("B"); root.rightNode = new Node("C"); Node tnode = root.leftNode; tnode.leftNode = new Node("D"); tnode.rightNode = new Node("E"); Node tempNode = tnode.rightNode; //remember "E" tnode = tnode.leftNode; tnode.leftNode = new Node ("H"); tnode.rightNode = new Node ("I"); tnode = tempNode; tnode.leftNode = new Node ("J"); tnode.rightNode = new Node ("K"); tnode = root.rightNode; tnode.leftNode = new Node("F"); tnode.rightNode = new Node("G"); tempNode = tnode.rightNode; // rememebr "G" tnode = tnode.leftNode; tnode.leftNode = new Node("L"); tnode.rightNode = new Node("M"); tnode = tempNode; tnode.leftNode = new Node("N"); tnode.rightNode = new Node("O"); return root; } }