Construction Algorithm

The algorithm:

$1.$ Root = first element of preorder

$2.$ Find root's index in inorder

$3.$ Split inorder into left and right parts

$4.$ Split preorder based on this (by counting elements)

$5.$ Recurse

function buildTree(preorder, inorder):
    if preorder is empty:
        return null
    rootVal = preorder[0]
    root = TreeNode(rootVal)
    mid = indexOf(inorder, rootVal)
    root.left = buildTree(preorder[1..mid], inorder[0..mid-1])
    root.right = buildTree(preorder[mid+1..end], inorder[mid+1..end])
    return root

Optimization: use a hash map for $O(1)$ index lookup in inorder. Pass indices instead of slicing arrays.

Time: $O(n)$ with hash map. Space: $O(n)$.