Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Example:

    in-order:   4 2 5 (1) 6 7 3 8
    pre-order: (1)2 4  5  3 6 7 8

From the example we can see the first element in the pre-order traversal is the root node, so we need to find the root node in in-order array, then split the in-order array into left subtree and rightsubtree, then recursively find the root node in left subtree and in right subtree.

public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(0, inorder.length-1, inorder, 0, preorder.length-1, preorder);
    }

    public TreeNode buildTree(int inStart, int inEnd, int[] inorder, int preStart, int preEnd, int[] preorder) {
        if(inStart > inEnd || preStart > preEnd) {
            return null;
        } 

        int rootValue = preorder[preStart];
        int rootIndexInorder = 0;

        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootValue) {
                rootIndexInorder = i;
                break;
            }
        }
        //left sub tree length
        int leftLength = rootIndexInorder - inStart;
        TreeNode root = new TreeNode(rootValue);
        root.left = buildTree(inStart, rootIndexInorder-1, inorder, preStart+1, preStart+leftLength, preorder);
        root.right = buildTree(rootIndexInorder+1, inEnd, inorder, preStart+leftLength+1, preEnd, preorder);

        return root;
    }