gistfile1.txt

public class Main {

	/* Static variable which acts as the pointer for the postOrder list */
	static int preIndex = 5;

	public static void main(String[] args) {

		/* InOrder Array */
		char[] inOrder = { 'D', 'B', 'E', 'A', 'F', 'C' };
		/* PostOrder Array */
		char[] postOrder = { 'D', 'E', 'B', 'F', 'C', 'A' };

		/* Call the BinaryTreeGeneratot recursive function! */
		Node root = BinaryTreeGenerator(inOrder, postOrder, 0,
				inOrder.length - 1);

		/* Prove the tree exists */
		printInorder(root);

	}

	/* Print inorder for proof */
	public static void printInorder(Node root) {

		if (root != null) {
			printInorder(root.left);
			System.out.println(root.data);
			printInorder(root.right);
		}

	}

	/*
	 * This is the function which actually does all the work. Lets go through it
	 * one at a time.
	 */

	public static Node BinaryTreeGenerator(char[] inOrder, char[] postOrder,
			int inStrt, int inEnd) {

		/*
		 * If the start of the array is bigger than the end of the array then
		 * obviously we need to end the recursion
		 */

		if (inStrt > inEnd) {

			return null;

		}

		/*
		 * Here we make the new node data space and allocate the value of a
		 * preIndex variable and then we post decrement it so as to point to the
		 * next element in the postOrder array
		 */

		Node node = new Node(postOrder[preIndex--]);

		/*
		 * If the start is equal to the end, its clear that we do need to end
		 * the recursive loop and return the current node
		 */

		if (inStrt == inEnd) {

			return node;

		}

		/*
		 * We call the search function to return to us the element where the
		 * data of the node is placed in the inOrder array
		 */
		
		int inIndex = search(inOrder, inStrt, inEnd, node.data);

		/*
		 * Call the recursive function to return the next set of nodes and place
		 * them right to left
		 */
		
		node.right = BinaryTreeGenerator(inOrder, postOrder, inIndex + 1, inEnd);
		node.left = BinaryTreeGenerator(inOrder, postOrder, inStrt, inIndex - 1);

		return node;

	}

	/*
	 * This function goes through the inorder array passed and returns the value
	 * where the value of the data hits the value of the element of the array
	 * which is passed in the parameter list, the values are checked only till
	 * the inEnd variable because we want to go from start to the end
	 */

	public static int search(char[] inOrder, int inStrt, int inEnd, char data) {

		for (int i = inStrt; i <= inEnd; i++) {

			if (inOrder[i] == data) {

				return i;

			}

		}

		return 0;
		
	}

}

/*
 * This is the node which we are going to consider as our ADT (Abstract Data
 * Type) It has a Data Space, A Right Node Pointer, A Left Node Pointer It also
 * has a constructor which sets the data, the left and right pointers as null
 */

class Node {

	char data;
	Node right;
	Node left;

	Node(char data) {

		this.data = data;
		this.left = null;
		this.right = null;

	}

}