Tree Traversal : InOrder, PreOrder, PostOrder using recursion and non-recursion for XProject. Non-recursive PostOrder is not included.

Tree Traversal

package tree;

public class TreeTraversal
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub

		// NOT BST
//		Node tree = new Node(3);
//		tree.left = new Node(2);
//		tree.right = new Node(5);
//		tree.left.left = new Node(1);
//		tree.left.right = new Node(4);
//		System.out.println("Is this BST : " + tree.isBinarySearchTree());

		// BST
		Node tree = new Node(4);
		tree.left = new Node(2);
		tree.right = new Node(5);
		tree.left.left = new Node(1);
		tree.left.right = new Node(3);
		System.out.println("Is this BST : " + tree.isBinarySearchTree());

		System.out.println("PreOrder");
		tree.preOrder();
		System.out.println("InOrder");
		tree.inOrder();
		System.out.println("InOrder Recursive");
		tree.inOrderRecursive(tree);
		System.out.println("PreOrder Recursive");
		tree.preOrderRecursive(tree);
		System.out.println("PostOrder Recursive");
		tree.postOrderRecursive(tree);

	}

}

package tree;

import java.util.Stack;

public class Node
{
	public int value;
	public Node left;
	public Node right;

	public Node(int aValue)
	{
		value = aValue;
	}

	/**
	 * BST is sorted tree with rules left  root
	 * 
	 * @return
	 */
	public boolean isBinarySearchTree()
	{
		boolean returnValue = true;
		Stack stack = new Stack();
		Node current = this;
		Node prev = null;
		// Loop through tree
		while (current != null || !stack.isEmpty())
		{
			if (current != null)
			{
				stack.push(current);
				current = current.left;
			}
			else
			{
				current = stack.pop();
				if (prev != null && prev.value > current.value)
				{
					returnValue = false;
				}
				prev = current;
				System.out.println(current.value);
				current = current.right;
			}
		}
		return returnValue;
	}

	public void inOrder()
	{
		Stack stack = new Stack();
		Node current = this;
		// Loop through tree
		while (current != null || !stack.isEmpty())
		{
			if (current != null)
			{
				stack.push(current);
				current = current.left;
			}
			else
			{
				current = stack.pop();
				System.out.println(current.value);
				current = current.right;
			}
		}
	}

	/**
	 * PreOrder : root, left, right Point : Before move the pointer, print root
	 * and left and right. Stack becomes bag place when there is nothing more
	 * child.
	 */
	public void preOrder()
	{
		Stack stack = new Stack();
		Node current = this;

		while (current != null || !stack.isEmpty())
		{
			if (current != null)
			{
				stack.push(current.right);
				System.out.println(current.value);
				current = current.left;
			}
			else
			{
				current = stack.pop();
			}
		}
	}

	public void inOrderRecursive(Node aCurrent)
	{
		if (aCurrent == null)
		{
			return;
		}
		inOrderRecursive(aCurrent.left);
		System.out.println(aCurrent.value);
		inOrderRecursive(aCurrent.right);
	}

	public void preOrderRecursive(Node aCurrent)
	{
		if (aCurrent == null)
		{
			return;
		}
		System.out.print(aCurrent.value + "\n");
		preOrderRecursive(aCurrent.left);
		preOrderRecursive(aCurrent.right);
	}

	public void postOrderRecursive(Node aCurrent)
	{
		if (aCurrent == null)
		{
			return;
		}
		postOrderRecursive(aCurrent.left);
		postOrderRecursive(aCurrent.right);
		System.out.print(aCurrent.value + "\n");
	}

}