Tree Traversal - Depth First (Iterative/ Non Recursive Approach)

In this particular articular we will discuss the iterative or non recursive approach to traverse a binary tree. We can traverse through a binary tree using stack. 
There are three ways in which a tree can be traversed using depth first approach.

1. Inorder (Left, Root, Right)
2. Preorder (Root, Left, Right)
3. Postorder (Righ, Left, root)

We have already discussed the details about all three approaches and traversal using recursive approach in our previous article - Tree Traversals - Depth First (Recursive Approach).

We will implement the iterative approach using stack.

Implementation - 

package ds.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BStree {

	private Node root;

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}

	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
		}
	}

	public void insert(int data) {
		Node nNode = new Node(data);
		
		Node root = this.root;
		Node nodeB = null;
		while (root != null) {
			nodeB = root;
			if (root.data > data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		if(data > nodeB.data)
			nodeB.left = nNode;
		else
			nodeB.right = nNode; 
	}
	
	public void inorderIterative() {
		Stack<Node> stack = new Stack<BStree.Node>();
		Node cNode = this.root;
		
		while(cNode != null || !stack.isEmpty()) {
			
			while(cNode != null) {
				stack.push(cNode);
				cNode = cNode.left;
			}
			Node pNode = stack.pop();
			System.out.print(pNode.data + " ");
			cNode = pNode.right;
		}
	}
	
	public void preOrderIterative() {
		Stack<Node> stack = new Stack<BStree.Node>();
		stack.push(this.root);
		
		while(!stack.empty()) {
			Node pNode = stack.pop();
			System.out.print(pNode.data + " ");
			if(pNode.right != null)
				stack.push(pNode.right);
			if(pNode.left != null)
				stack.push(pNode.left);
		}
	}
	
	public void postOrderIterative() {
		Stack<Node> stack = new Stack<BStree.Node>();
		stack.push(this.root);
		
		Stack<Node> stack2 = new Stack<BStree.Node>();
		
		while(!stack.empty()) {
			Node pNode = stack.pop();
			stack2.push(pNode);
			if(pNode.left != null)
				stack.push(pNode.left);
			if(pNode.right != null)
				stack.push(pNode.right);
		}
		
		while(!stack2.isEmpty()) {
			System.out.print(stack2.pop().data + " ");
		}
	}
}

Now to test the implementation we can write a main method which will print the binary tree keys using all three depth first approaches using iterative methods. We will be using same data for creating the binary tree which has been used in previous articles.
For reference take a look at the figure of binary tree given below which we will traverse in our main method -

Main Method -

package ds.tree;

public class BtreeMain {
	
	public static void main(String[] args) {
		BStree bst = new BStree(5);
		bst.insert(3);
		bst.insert(8);
		bst.insert(6);
		bst.insert(4);
		bst.insert(2);
		bst.insert(10);
		
		System.out.println("Iterative Inorder -");
		bst.inorderIterative();
		
		System.out.println("\nIterative Inorder -");
		bst.preOrderIterative();
		
		System.out.println("\nIterative Postorder -");
		bst.postOrderIterative();
	}
}

Output: 

Iterative Inorder -
2 3 4 5 6 8 10 
Iterative Preorder -
5 3 2 4 8 6 10 
Iterative Postorder -
2 4 3 6 10 8 5 

You can take a look at the figure given above to test the output. Trees can be traversed in breadth first fashion also which has already been covered in this article - Tree Traversals - Breadth First or level order