Construct Binary Tree from Preorder and Inorder Traversal

This challenge asks you to reconstruct a binary tree given its preorder and inorder traversals. This is a classic tree problem that tests your understanding of tree structures and recursive algorithms. It's useful in scenarios where you only have traversal information available and need to rebuild the original tree.

Problem Description

You are given two integer arrays, preorder and inorder, representing the preorder and inorder traversals of a binary tree, respectively. Your task is to construct and return the binary tree. The preorder traversal lists the nodes in the order they are visited (root, left, right), while the inorder traversal lists the nodes in the order they are visited (left, root, right).

What needs to be achieved:

• Create a binary tree data structure.
• Populate the tree nodes with values from the given preorder and inorder arrays.
• Return the root node of the constructed binary tree.

Key Requirements:

• The preorder and inorder arrays must be valid traversals of the same binary tree.
• The preorder array's length must be equal to the inorder array's length.
• The tree should be constructed recursively.

Expected Behavior:

The function should return the root node of the reconstructed binary tree. If either input array is empty, return null.

Edge Cases to Consider:

• Empty input arrays.
• Single-node trees.
• Trees with skewed (left or right) structures.
• Duplicate values in the input arrays (though this is generally not expected in a standard binary tree problem, consider how your solution handles it).

Examples

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: A binary tree with root node value 3, left child with value 9, right child with value 20, 20's left child with value 15, and 20's right child with value 7, and 9's left child with value null, 9's right child with value null, 15's left child with value null, 15's right child with value null, 7's left child with value null, and 7's right child with value null.
Explanation: The root is 3. In inorder, 3's left subtree is [9], and its right subtree is [20, 15, 7].  9's left and right are null. 20's left is 15, and 20's right is 7.

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: A binary tree with root node value -1 and no children.
Explanation: A single-node tree is straightforward.

Example 3: (Skewed Tree)

Input: preorder = [1,2,3] , inorder = [3,2,1]
Output: A binary tree where 1 is the root, 2 is its left child, and 3 is 2's left child.
Explanation: This demonstrates handling a right-skewed tree.

Constraints

• 1 <= preorder.length <= 300
• preorder.length == inorder.length
• -100 <= preorder[i], inorder[i] <= 100
• All the integer values in preorder and inorder are unique.

Notes

• Consider using recursion to solve this problem. The preorder traversal provides the root of each subtree, and the inorder traversal helps you identify the left and right subtrees.
• The index of the root in the inorder traversal is crucial for dividing the problem into smaller subproblems.
• Think about how to handle the base case (when the input arrays are empty or contain only one element).
• A binary tree node structure is assumed to exist, with properties like val, left, and right. You don't need to define this structure; just assume it's available.
• The goal is to reconstruct the entire tree, not just determine its structure.

Pseudocode:

function buildTree(preorder, inorder):
  if preorder is empty:
    return null

  root_val = preorder[0]
  root = new TreeNode(root_val)

  root_index_in_inorder = findIndex(inorder, root_val)

  # Left subtree
  left_inorder = inorder[:root_index_in_inorder]
  right_inorder = inorder[root_index_in_inorder + 1:]

  left_preorder = preorder[1:root_index_in_inorder + 1]
  right_preorder = preorder[root_index_in_inorder + 1:]

  root.left = buildTree(left_preorder, left_inorder)
  root.right = buildTree(right_preorder, right_inorder)

  return root

function findIndex(arr, val):
  # Helper function to find the index of a value in an array
  for i from 0 to arr.length - 1:
    if arr[i] == val:
      return i
  return -1 # Should not happen given the constraints