CC-8 : Traverse Binary Tree via In-order/ Depth First traversal.

Description:

As part of In-order (also known as DepthFirst) all nodes are iteratively/ recursively traversed in order of left node, parent node, right node. Given an input Binary Tree, traverse the tree in In-order.

Test cases and expected outputs:

Input Parameters	Expected outputs
	InOrder traversal : 33, 6, 5, 78, 4, 8, 14, 9, 18 ,16, 7

Pseudocode:

Initialize an ArrayList to hold the result of the In-order traversal.

Initialize a Stack to temporarily hold Tree Nodes that are being processed in LIFO order.

Initialize current node variable to root of input Binary Tree.

Iterate through stack nodes using an endless while loop:

If current node is not null, add the current node to the stack. Update current node to point to its own left child.

Else :

If stack size is empty, we have traversed the whole tree, so exit the while loop.

Set current node to first node of the Stack.

Add current node’s node data to In-order traversal ArrayList.

Update current node to point to its own right child.

Return In-order traversal ArrayList.

Code:

public ArrayList<Integer> inOrderIterative(BinTreeNode root) throws Exception{
	if (root==null) {return null;}
	ArrayList<Integer> inOrder=new ArrayList<Integer>();
	Deque<BinTreeNode> stack=new LinkedList<BinTreeNode>();
	BinTreeNode node=root;
	while (true) {
		if (node != null) {
			stack.offerFirst(node);
			node=node.getLeftChild();
		}else {
			if (stack.size()==0) {
				break;
			}
			node=stack.pollFirst();
			inOrder.add(node.getNodeData());
			node=node.getRightChild();
		}
	}
		
	return inOrder;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class BinTreeInOrderIterative {	

public ArrayList<Integer> inOrderIterative(BinTreeNode root) throws Exception{
	if (root==null) {return null;}
	ArrayList<Integer> inOrder=new ArrayList<Integer>();
	Deque<BinTreeNode> stack=new LinkedList<BinTreeNode>();
	BinTreeNode node=root;
	while (true) {
		if (node != null) {
			stack.offerFirst(node);
			node=node.getLeftChild();
		}else {
			if (stack.size()==0) {
				break;
			}
			node=stack.pollFirst();
			inOrder.add(node.getNodeData());
			node=node.getRightChild();
		}
	}
		
	return inOrder;
}

public static void printArrayListSummary(ArrayList al, String label) throws Exception {
	if (al == null) { System.out.println("\n\n Input ArrayList was null !! \n"); return; }
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < al.size(); arrayIndex++) {
			System.out.print(al.get(arrayIndex));
			if (arrayIndex < al.size()-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}
 	
public static void main(String[] args) {
	/************************
 	Test cases given below:
	 **********************/
	ArrayList<Integer> retVal=null;
	try {
	BinTreeInOrderIterative po=new BinTreeInOrderIterative();
	BinTreeNode root=po.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(po.new BinTreeNode(5));
	root.setRightChild(po.new BinTreeNode(7));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(po.new BinTreeNode(6));
	root.getLeftChild().setRightChild(po.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(po.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(po.new BinTreeNode(14));	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(po.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(po.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(po.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(po.new BinTreeNode(9));
	
	retVal=po.inOrderIterative(root);
	printArrayListSummary(retVal, "InOrder traversal");	
	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}

public class BinTreeNode {
	private BinTreeNode leftNode=null;
	private BinTreeNode rightNode=null;
	private int nodeData=0;
	
	public BinTreeNode(int data) {
		nodeData=data;
	}	
	public BinTreeNode getLeftChild() {
		return leftNode;
	}
	public void setLeftChild(BinTreeNode leftNode) {
		this.leftNode = leftNode;
	}
	public BinTreeNode getRightChild() {
		return rightNode;
	}
	public void setRightChild(BinTreeNode rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}

}
	
}