# 105. Construct Binary Tree from Preorder and Inorder Traversal Leetcode Solution

## Construct Binary Tree from Preorder and Inorder Traversal Leetcode 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.

## Construct Binary Tree from Preorder and Inorder Traversal Leetcode Solution :

### Constraints :

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

### Example 1:

• Input: preorder = [-1], inorder = [-1]
• Output: [-1]

Intuition :

Inorder traversal is a special traversal that helps us to identify a node and its left and right subtree. Preorder traversal always gives us the root node as the first element. Using these properties we can construct the unique binary tree.

Approach :

1. Create a map to store the inorder indexes.
2. Call the function constructTree with all 7 parameters as shown above.
3. In the recursive function, first check the base case, if (preStart,>preEnd || inStart> inEnd) then return NULL.
4. Construct a node (say root) with the root value( first element of preorder).
5. Find the index of the root, say elem from the hashmap.
6. Find the number of elements ( say nElem) in the left subtree = elem – inStart
7. Call recursively for the left subtree with correct values (shown in the above table) and store the answer received in root->left.
8. Call recursively for the right subtree with correct values (shown in the above table) and store the answer received in root->right.
9. Return root

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others