Construct a binary tree given its preorder and inorder traversals.

Our solution to construct a binary tree from pre-order and in-order traversal arrays uses a recursive approach. We first identify the root node from the pre-order array, then split the in-order array into left and right subtrees based on the root's position in the in-order array. We continue this process recursively to build the entire binary tree.

• We start by picking the first element of the preorder array as the root of the tree. The index of this root element in the inorder array helps us divide the tree into left and right subtrees.
• The elements to the left of the root in the inorder array form the left subtree, and the elements to the right form the right subtree.
• We then recursively build the left and right subtrees using the next available elements in the preorder array.

To ensure efficient lookups of the root's index in the inorder array, we create a hash map (inorder_index_map) that maps values to their indices in the inorder array. This allows us to retrieve the position of the root in constant time.

By maintaining the correct indices for both the pre-order and in-order arrays, we can recursively construct the entire tree.

Time Complexity: The solution has a time complexity of O(n), where n is the number of elements in the tree. This is because we traverse both the preorder and inorder arrays once, and we use a hash map for constant-time lookups of root indices in the inorder array.

Space Complexity: The solution uses O(n) space for the hash map that stores the indices of elements in the inorder array, and the recursion stack requires O(h) space, where h is the height of the tree. In the worst case (a skewed tree), the height of the tree can be O(n), so the total space complexity is O(n).