# LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

**The Problem**

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*.

**Example**

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

**Constraints:**

`1 <= preorder.length <= 3000`

`inorder.length == preorder.length`

`-3000 <= preorder[i], inorder[i] <= 3000`

`preorder`

and`inorder`

consist ofvalues.**unique**- Each value of
`inorder`

also appears in`preorder`

. `preorder`

isto be the preorder traversal of the tree.**guaranteed**`inorder`

isto be the inorder traversal of the tree.**guaranteed**

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < inorder.size(); ++i)
inorderIndexMap[inorder[i]] = i;
int preorderIndex = 0;
return buildTreeHelper(
preorder, inorder,
preorderIndex,
0, inorder.size() - 1,
inorderIndexMap
);
}
TreeNode* buildTreeHelper(
vector<int>& preorder, vector<int>& inorder,
int& preorderIndex,
int left, int right,
unordered_map<int, int>& inorderIndexMap
) {
if (left > right) return NULL;
int rootValue = preorder[preorderIndex];
TreeNode* root = new TreeNode(rootValue);
int inorderIndex = inorderIndexMap[rootValue];
++preorderIndex;
root->left = buildTreeHelper(
preorder, inorder,
preorderIndex,
left, inorderIndex - 1,
inorderIndexMap
);
root->right = buildTreeHelper(
preorder, inorder,
preorderIndex,
inorderIndex + 1, right,
inorderIndexMap
);
return root;
}
```

ðŸ§

Github with all the solution including test cases.

Explanation:

- The
`buildTree`

function is the entry point for constructing the binary tree. It takes the`preorder`

and`inorder`

vectors as inputs. - An
`unordered_map`

named`inorderIndexMap`

is created to store the indices of values in the`inorder`

array. This map will allow us to quickly find the position of a value in the`inorder`

traversal. - A
`for`

loop iterates through the`inorder`

array to populate`inorderIndexMap`

with values and their corresponding indices. - The
`preorderIndex`

variable is initialized to 0. It keeps track of the current position in the`preorder`

array. - Finally, the
`buildTreeHelper`

function is called with the necessary parameters to construct the binary tree. - The
`buildTreeHelper`

function is a recursive function responsible for constructing a subtree of the binary tree. - It takes parameters including the
`preorder`

and`inorder`

vectors, the`preorderIndex`

(used to track the position in the`preorder`

array), and the`left`

and`right`

indices (indicating the range of values in the current subtree). - The base case checks if the
`left`

index exceeds the`right`

index, in which case it returns`NULL`

to indicate an empty subtree. - It retrieves the root value from the
`preorder`

array and creates a new`TreeNode`

with that value. - It finds the position of the root value in the
`inorder`

array using`inorderIndexMap`

. - The
`preorderIndex`

is incremented to move to the next value in the`preorder`

array. - The function then recursively constructs the left and right subtrees by adjusting the
`left`

and`right`

indices accordingly. - Finally, it returns the root of the constructed subtree.