CareerCup

The answer is yes and the solution is:
1. Take the first element of the pre-order list
2. Find that element in in-order list and split that list into two lists - in-order before and in-order after
3. Similarly, for the pre-order list remove the first element and split it into two parts of the same length as in point 2 - pre-order before and pre-order after
4. Apply this function recursively to "before" and "after" lists

if the binary tree is sorted, you can just insert the nodes in order of the pre-order list.

Just keep inserting the pre-order traversal elements to a tree.

public static Node BuildTree(int[] preOrder)
	{
		Node result = null;
		foreach(int data in preOrder)
		{
			result = BST_PreOrderInsert(result, data);
		}
	}

	private static Node BST_PreOrderInsert(Node head, int data)
	{
		if(head == null)
			return new Node(data);

		Node current = head;	
		Node prev = null;
		
		while(current != null)
		{
			prev = current ;
			if(current .Data >= data)
			{
				current = current .Right;
			}
			else
			{
				current = current .Left;
			}
		}

		if(prev.Data >= data)
		{
			prev.Rigth = new Node(data);
		}
		else
		{
			prev.Right = new Node(data);
		}

		return head;
	}
}

if your printout has duplicates -- it is not possible to reconstruct the tree

Here is another solution that uses HashMap to avoid the fin() calls into in-order array. But this wont work for dupliate elements in the tree

public class TreeExercise {
	
	private HashMap<Integer, Integer> inOrderElementPositionMap = new HashMap<Integer, Integer>(); 
	
	private int preOrderPointer = 0;
	
	public BinaryTree<Integer> buildTree(String inOrderPrint, String preOrderPrint) {
		String[] inOrderStrings = inOrderPrint.split(" ");
		String[] preOrderStrings = preOrderPrint.split(" ");
		int[] inOrderNumbers = new int[inOrderStrings.length];
		int[] preOrderNumbers = new int[inOrderStrings.length];
		for (int i=0 ; i<inOrderStrings.length ; i++) {
			inOrderNumbers[i] = Integer.parseInt(inOrderStrings[i]);
			preOrderNumbers[i] = Integer.parseInt(preOrderStrings[i]);
		}
		//load in-order array into a map
		loadInOrderElementPositionMap(inOrderNumbers);
		//build the tree
		Node<Integer> root = buildTree(inOrderNumbers, 0, inOrderNumbers.length-1, preOrderNumbers);
		
		return new BinaryTree<Integer>(root);
	}
	
	/**
	 * load the in-order array into a hashmap mapping the element to position in the array
	 * @param inOrderNumbers
	 */
	private void loadInOrderElementPositionMap(int[] inOrderNumbers) {
		for (int i = 0 ; i < inOrderNumbers.length ; i++) {
			inOrderElementPositionMap.put(inOrderNumbers[i], i);
		}
	}
	
	/**
	 * 
	 * @param inOrder - inorder array
	 * @param start - start element in the inorder array for this method execution
	 * @param end - end element in the inorder array for this method execution
	 * @param preOrder - preorder array
	 * @return
	 */
	private Node<Integer> buildTree(int[] inOrder, int start, int end, int[] preOrder) {
		Node<Integer> node = null;
		if (start <= end && preOrderPointer < preOrder.length) {
			int element = preOrder[preOrderPointer];
			int position = inOrderElementPositionMap.get(element);
			if (position >= start && position <= end) {
				//build the Node for this element if we find a match
				node = new Node<Integer>(element);
				//increment the iterating pointer only where there is a match
				preOrderPointer++;
				//now divide the array into two subtrees, and build nodes for each of them recursively
				node.left = buildTree(inOrder, 0, position-1, preOrder);
				node.right = buildTree(inOrder, position+1, end, preOrder);
			}
		}
		return node;
	}
	
	public static void main(String[] args) {
		Node<Integer> root = new Node<Integer>(10);
		Node<Integer> node4 = new Node<Integer>(4);
		root.left = node4;
		Node<Integer> node5 = new Node<Integer>(5);
		root.right = node5;
		Node<Integer> node6 = new Node<Integer>(6);
		Node<Integer> node9 = new Node<Integer>(9);
		node4.left = node6;
		node4.right = node9;
		
		Node<Integer> node11 = new Node<Integer>(11);
		Node<Integer> node3 = new Node<Integer>(3);
		node5.left = node11;
		node5.right = node3;
		
		Node<Integer> node1 = new Node<Integer>(1);
		Node<Integer> node7 = new Node<Integer>(7);
		node6.left = node1;
		node9.right = node7;
		BinaryTree<Integer> tree = new BinaryTree<Integer>(root);
		System.out.print("InOrder  : ");
		tree.printInOrder();
		System.out.println();
		System.out.print("PreOrder : ");
		tree.printPreOrder();
		TreeExercise exercises = new TreeExercise();
		System.out.println("\ncreating new tree...");
		BinaryTree<Integer> newTree = exercises.buildTree("1 6 4 9 7 10 11 5 3", "10 4 6 1 9 7 5 11 3");
		System.out.println("New Tree");
		System.out.print("InOrder  : ");
		newTree.printInOrder();
		System.out.println();
		System.out.print("PreOrder : ");
		newTree.printPreOrder();
		
	}