Construct Binary Tree from Preorder and Inorder Traversal

Problem Description

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, construct and return the binary tree.

Key Insights

• The first element of the preorder array is always the root of the binary tree.
• The position of this root element in the inorder array helps determine the left and right subtrees.
• Elements to the left of the root in inorder form the left subtree, while elements to the right form the right subtree.
• This process can be solved recursively by constructing the tree via the preorder and inorder arrays.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as we traverse each node once. Space Complexity: O(n), for the recursion stack in the worst case (unbalanced tree) and O(n) for the hashmap used to store indices of inorder elements.

Solution

To construct the binary tree, we can use a recursive approach. We will maintain a pointer for the current root from the preorder array and use a hashmap to store the indices of elements in the inorder array for quicker access. The steps are:

1. Start with the first element of preorder as the root.
2. Find the index of this root in inorder to determine the left and right subtree boundaries.
3. Recursively construct the left and right subtrees using the respective segments of the preorder and inorder arrays.

Code Solutions