Construct Binary Tree from Preorder and Inorder Traversal

time Complexity: O(n^2). Worst case occurs when tree is left skewed

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (inorder.length != preorder.length) {
            return null;
        }
        return myBuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
        //i need some inromation I rewrote recusion ufnciton
    }

    private TreeNode myBuildTree(int[] inorder, int instart, int inend, int[] preorder, int prestart, int preend) {
        if (instart > inend) {
            return null;
        }


        //find root first then left， then right， if we know root ，in theorder tree we find the root left will allof the subree
        //wrote onefunction to find speicfit root


        TreeNode root = new TreeNode(preorder[prestart]);
        int position = findPosition(inorder, instart, inend, preorder[prestart]);

        root.left = myBuildTree(inorder, instart, position - 1, preorder, prestart + 1, prestart + position - instart);
        root.right = myBuildTree(inorder, position + 1, inend, preorder, prestart + position - instart + 1, preend);
        //position-instart lefttree node number ＋ start it is start number
        return root;
    }



    //find root first then left， then right， if we know root ，in theorder tree we find the root left will allof the subree
    //wrote onefunction to find speicfit root


        private int findPosition(int[] arr, int start, int end, int key) {
            int i;
            for (i = start; i <= end; i++) {
                if (arr[i] == key) {
                    return i;
                }
            }
            return -1;
        }