Construct Binary Tree from Preorder and Inorder Traversal

Given the preorder and inorder traversal sequences of a binary tree, reconstruct the original tree. This is a fundamental problem in tree manipulation and is crucial for problems involving serialization, deserialization, and various tree-based algorithms.

Problem Description

You are given two integer arrays, preorder and inorder, where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree. Your task is to reconstruct and return the binary tree.

Key Requirements:

• The values in the nodes are unique.
• You need to build the tree structure based on the provided traversal sequences.
• Return the root node of the reconstructed binary tree.

Expected Behavior:

• If the input arrays are empty, you should return null (or an equivalent representation of an empty tree).
• The reconstructed tree should exactly match the tree that generated these traversals.

Edge Cases to Consider:

• Empty input arrays.
• A tree with only one node.
• Trees that are skewed (e.g., a linked list).

Examples

Example 1:

Input:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

Output:
A binary tree with root node 3.
Left child of 3 is 9.
Right child of 3 is 20.
Left child of 20 is 15.
Right child of 20 is 7.

   3
  / \
 9  20
   /  \
  15   7

Explanation: In preorder, the first element 3 is always the root. In inorder, 3 separates the left subtree ([9]) from the right subtree ([15, 20, 7]). We then recursively apply this logic to the left and right subtrees. For the right subtree, 20 is the root, and in its inorder traversal [15, 20, 7], 20 separates 15 (left child) from 7 (right child).

Example 2:

Input:
preorder = [1]
inorder = [1]

Output:
A binary tree with root node 1.

   1

Explanation: With only one element, it's the root and the only node in the tree.

Example 3:

Input:
preorder = []
inorder = []

Output:
null

Explanation: An empty traversal sequence results in an empty tree.

Constraints

• preorder.length == inorder.length
• 1 <= preorder.length <= 3000 (This implies inorder.length will also be within this range)
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder[i] and inorder[i] are unique.
• inorder guarantees that it is a valid inorder traversal of a binary tree.
• preorder guarantees that it is a valid preorder traversal of a binary tree.

Notes

• Remember that in a preorder traversal, the root is visited first, then the left subtree, then the right subtree.
• In an inorder traversal, the left subtree is visited first, then the root, then the right subtree.
• The key to this problem lies in identifying the root of each subtree from the preorder traversal and then using the inorder traversal to determine which elements belong to its left and right subtrees.
• Consider using a helper function that takes indices or slices of the arrays to define the current subtree being processed.
• An efficient way to find the index of the root in the inorder traversal would be beneficial.