Background
In last post Binary Tree Traversal we saw recursive method to print the tree. We saw DFS(Depth first search) approach which included pre order, post order and in order traversal and we also saw BFS(Breath first search) approach which includes level order traversal.In this post we will see an iterative way of implementing the DFS approach. Implementation is very simple and uses stack data structure.
Code :
package Tree;
import java.util.Stack;
/**
* Created by Aniket on 3/14/14.
*/
public class IterativeTreePrinter {
public static void printIterativePreOrderTraversal(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null){
System.out.println("Date : " + root.getData());
if(root.getRightNode() != null){
stack.push(root.getRightNode());
}
if(root.getLeftNode() != null){
stack.push(root.getLeftNode());
}
if(!stack.isEmpty()){
root = stack.pop();
}
else {
root = null;
}
}
}
public static void printIterativeInOrderTraversal(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(!stack.isEmpty() || root != null){
if(root != null){
stack.push(root);
root = root.getLeftNode();
}
else {
root = stack.pop();
System.out.println("Data : " + root.getData());
root = root.getRightNode();
}
}
}
public static void printIterativePostOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode peekNode = null;
TreeNode lastVisitedNode = null;
while(!stack.isEmpty() || root != null){
if(root != null){
stack.push(root);
root = root.getLeftNode();
}
else {
peekNode = stack.peek();
if(peekNode.getRightNode() != null && peekNode.getRightNode() != lastVisitedNode){
root = peekNode.getRightNode();
}
else {
stack.pop();
System.out.println("Data : " + peekNode.getData());
lastVisitedNode = peekNode;
}
}
}
}
}
Output :
Output consumes lot of line as I am printing each data in a single line. So I am skipping it in this case. I have tested and verified the code. Output is same as that of recursive method. You can check the output provided in the post( Binary Tree Traversal ).
Related Links
Binary Tree Traversal
Binary Tree Traversal
Binary Tree Traversal
