gistfile1.txt

public class Main {
	
	/*Static variable which acts as the pointer for the preorder list*/
	static int preIndex = 0;

	public static void main(String[] args) {
		
		/*Inorder Array*/
		char[] inOrder = { 'D', 'B', 'E', 'A', 'F', 'C' };
		/*Preorder Array*/
		char[] preOrder = { 'A', 'B', 'D', 'E', 'C', 'F' };

		/*Call the BinaryTreeGeneratot recursive function!*/
		Node root = BinaryTreeGenerator(inOrder, preOrder, 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);
			printInorder(root.right);
			System.out.println(root.data);
		}
	
	}
	
	/*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[] preOrder,
			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 increment it so as to point to the next element in the 
		 * preorder array*/
		
		Node node = new Node(preOrder[preIndex++]);

		/*If the start is equal to the end, its clear that we do need to end the 
		 *resursive 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
		 * left to right*/
		node.left = BinaryTreeGenerator(inOrder, preOrder, inStrt, inIndex - 1);
		node.right = BinaryTreeGenerator(inOrder, preOrder, inIndex + 1, inEnd);

		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;

	}

}