public class BinaryTree<T> {
	
	private static Node<Integer> root;

	private static class Node<T> {
		T data;
		Node<T> left;
		Node<T> right;
		
		public Node(T data) {
			this.data = data;
			left = null;
			right = null;
		}
	}
	
	private int findIndex(T target, T[] arr, int st, int end) {
		for (int i = st; i <= end; ++i) {
			if (arr[i].equals(target)) return i;
		}
		return -1;
	}

	public Node<T> buildFromInAndPreOrder(T[] in, T[] pre, int inSt, int inEnd, int preSt, int preEnd) {
		// Base case
		if (inEnd < inSt) return null;
		
		// Create root for the current subtree
		Node<T> node = new Node<T>(pre[preSt]);
		
		// Find the start and end indices for the left and right subtrees
		int inSplitIndex = findIndex(pre[preSt], in, inSt, inEnd);
		int leftSize = inSplitIndex - inSt;
//		int rightSize = inEnd - inSplitIndex;
		int preSplitIndex = preSt + 1 + leftSize;
		
		// build left and right subtrees
		node.left = buildFromInAndPreOrder(in, pre, inSt, inSplitIndex-1, preSt+1, preSplitIndex-1);
		node.right = buildFromInAndPreOrder(in, pre, inSplitIndex+1, inEnd, preSplitIndex, preEnd);

		return node;
	}
	
	public Node<T> buildFromInAndPostOrder(T[] in, T[] post, int inSt, int inEnd, int postSt, int postEnd) {
		// Base case
		if (inEnd < inSt) return null;
		
		// Create root for the current subtree
		Node<T> node = new Node<T>(post[postEnd]);

		// Find the start and end indices for the left and right subtrees
		int inSplitIndex = findIndex(post[postEnd], in, inSt, inEnd);
//		int leftSize = inSplitIndex - inSt;
		int rightSize = inEnd - inSplitIndex;
		int postSplitIndex = postEnd - 1 - rightSize;
		
		// build left and right subtrees
		node.left = buildFromInAndPostOrder(in, post, inSt, inSplitIndex-1, postSt, postSplitIndex);
		node.right = buildFromInAndPostOrder(in, post, inSplitIndex+1, inEnd, postSplitIndex+1, postEnd-1);

		return node;
	}

	public void inorder(Node<T> root) {
		if (root == null) return;
		inorder(root.left);
		System.out.print(root.data + ",");
		inorder(root.right);
	}
	
	public void preorder(Node<T> root) {
		if (root == null) return;
		System.out.print(root.data + ",");
		preorder(root.left);
		preorder(root.right);
	}

	public void postorder(Node<T> root) {
		if (root == null) return;
		postorder(root.left);
		postorder(root.right);
		System.out.print(root.data + ",");
	}

	public static void inorderAndPreorderExample() {
		System.out.println("Constructring a tree from inordr and preorder traversals:");
		Character[] in = new Character[]{'D', 'B','E', 'A', 'F', 'C'};
		Character[] pre = new Character[]{'A', 'B', 'D', 'E', 'C', 'F'};
		int len = in.length;

		BinaryTree<Character> builder = new BinaryTree<Character>();
		Node<Character> root = builder.buildFromInAndPreOrder(in, pre, 0, len-1, 0, len-1);

		System.out.println("Inorder traversal for the constructed tree:");
		builder.inorder(root);
		System.out.println();
		System.out.println("Preorder traversal for the constructed tree:");
		builder.preorder(root);
		System.out.println();
		System.out.println("=================================================\n");
	}

	public static void inorderAndPostorderExample() {
		System.out.println("Constructring a tree from inordr and postorder traversals:");
		Integer[] in =  new Integer[]{4, 8, 2, 5, 1, 6, 3, 7};
		Integer[] post =  new Integer[]{8, 4, 5, 2, 6, 7, 3, 1};
		int len = in.length;

		BinaryTree<Integer> builder = new BinaryTree<Integer>();
		Node<Integer> root = builder.buildFromInAndPostOrder(in, post, 0, len-1, 0, len-1);

		System.out.println("Inorder traversal for the constructed tree:");
		builder.inorder(root);
		System.out.println();
		System.out.println("Postorder traversal for the constructed tree:");
		builder.postorder(root);
		System.out.println();
		System.out.println("=================================================\n");
	}

    public static void findMaxSumExample() {
        BinaryTree<Integer> tree = new BinaryTree<Integer>();
        root = new Node<>(1);
        root.left = new Node<>(2);
        root.right = new Node<>(3);
        root.left.left = new Node<>(4);
        root.left.right = new Node<>(5);

       
       System.out.println("Inorder traversal of input tree is :");
        tree.inorder(root);
        System.out.println("");
        /* convert tree to its mirror */
        //findMaxSum(root);
        System.out.println(findMaxSum(root));
    }
    
    public static void mirrorExample() {
        BinaryTree<Integer> tree = new BinaryTree<Integer>();
        root = new Node<>(1);
        root.left = new Node<>(2);
        root.right = new Node<>(3);
        root.left.left = new Node<>(4);
        root.left.right = new Node<>(5);

       
       System.out.println("Inorder traversal of input tree is :");
        tree.inorder(root);
        System.out.println("");
        /* convert tree to its mirror */
        mirror(root);
        System.out.println("Inorder traversal of input tree is :");
        tree.inorder(root);
        System.out.println("");
    }
    
    public static void mirror(Node<Integer> n) {
        if (n != null) {
            mirror(n.left);
            mirror(n.right);
            Node<Integer> temp = n.right;
            n.right = n.left;
            n.left = temp;
        }
    }     
    
    public static int findMaxSum(Node<Integer> n) {
        if (n == null) return 0;
        else {
            int sumleft = findMaxSum(n.left);
            int sumright = findMaxSum(n.right);
            if (sumleft > sumright) return n.data + sumleft;
            else return n.data + sumright;
        }
    }
 
	public static void main(String[] args) {
		inorderAndPreorderExample();
		inorderAndPostorderExample();
		findMaxSumExample();
		mirrorExample();
	}
	
}