import java.lang.*;
import java.util.*;
import node.*;

class BuildTree {
	// My old solution
	/*
	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		TreeNode root = new TreeNode(preorder[0]);
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		int parentIndex = 1;
		boolean left = true;
		for (int i = 1; i < preorder.length; i++) {
			TreeNode node = new TreeNode(preorder[i]);
			for (int j = 0; j < inorder.length; j++) {
				if (node.val == inorder[j]) {
					if (j < parentIndex) {
						left = true;
						stack.peek().left = node;
						System.out.println("Left: " + node.val);
					} else if (left) {
						left = false;
						stack.pop();
						stack.peek().right = node;
						System.out.println("Right: " + node.val);
					} else {
						stack.peek().right = node;
						System.out.println(stack.peek().val);
						System.out.println("Right: " + node.val);
					}
					parentIndex = j;
					break;
				}
			}
			stack.push(node);
		}
		return root;
	}
	*/

	private static int preIndex = 0;

	public static int findInorder(int value, int[] inorder) {
		for (int i = 0; i < inorder.length; i++) {
			if (inorder[i] == value)
				return i;
		}
		return -1;
	}

	public static TreeNode
	buildTree(int[] preorder, int[] inorder, int start, int end) {
		if (start > end)
			return null;
		int value = preorder[preIndex++];
		TreeNode node = new TreeNode(value);
		if (start == end)
			return node;
		int mid = findInorder(value, inorder);
		node.left = buildTree(preorder, inorder, start, mid - 1);
		node.right = buildTree(preorder, inorder, mid + 1, end);
		return node;
	}

	public static void main(String[] args) {
		TreeNode leftLeaf = new TreeNode(9);
		TreeNode middleLeaf = new TreeNode(15);
		TreeNode rightLeaf = new TreeNode(7);
		TreeNode rightParent = new TreeNode(20, middleLeaf, rightLeaf);
		TreeNode root = new TreeNode(3, leftLeaf, rightParent);
		int[] preorder = {3, 9, 20, 15, 7};
		int[] inorder = {9, 3, 15, 20, 7};
		int n = preorder.length - 1;
		System.out.println(buildTree(preorder, inorder, 0, n).right.right.val);
	}
}