Build Tree from Preorder and Inorder: the idea to remember.

The core insight

Consume preorder roots in order. Locate each root in inorder to divide the current interval into its left and right subtrees.

Why it works

Preorder visits the root before both children. The inorder root position uniquely determines which remaining values belong to each side.

The mistake to avoid

Build the left subtree before the right, and keep the preorder cursor local to the invocation.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> position = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) position.put(inorder[i], i);
    return build(preorder, new int[]{0}, 0, inorder.length, position);
}
TreeNode build(int[] pre, int[] next, int from, int to, Map<Integer, Integer> pos) {
    if (from == to) return null;
    TreeNode root = new TreeNode(pre[next[0]++]);
    int middle = pos.get(root.val);
    root.left = build(pre, next, from, middle, pos);
    root.right = build(pre, next, middle + 1, to, pos);
    return root;
}

Make the next connection