Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays representing preorder (root, left sub-t, right sub-t) and inorder (left sub-t, root, right sub-t) traversal of the same binary tree, construct and return the binary tree.

• Preorder determines the root
• Inorder determines the structure (left and right subtrees)

class Solution {
    int preIndex;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // preorder root, left, right
        // inorder left, root, right
        // this is similar to the post order/ pre order but reversed
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        preIndex = 0;
        return buildTreeHelper(preorder, inorder, 0, inorder.length - 1);
    }
    
    TreeNode buildTreeHelper(int[] preorder, int[] inorder, int start, int end) {
        if (start > end) {
            return null;
        }
    
        var root = new TreeNode(preorder[preIndex++]);
        if (start == end) {
            return root;
        }

        int index = findValue(root.val, start, end, inorder);
        // order matters because we go left to right
        root.left = buildTreeHelper(preorder, inorder, start, index - 1);
        root.right = buildTreeHelper(preorder, inorder, index + 1, end);
        return root;
    }
    
    int findValue(int val, int start, int end, int[] inorder) {
        for (int i = start; i <= end ; i++) {
            if (val == inorder[i]) {
                return i;
            }
        }
        return -1; // should not get here
    }
}