# Day 8: Construct Binary Tree from Preorder and Inorder Traversal

*Problem Link:*

*Problem Statement:*

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 1:*

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

**Output:** [3,9,20,null,null,15,7]

*Example 2:*

**Input:** preorder = [-1], inorder = [-1]

**Output:** [-1]

*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

*My Solution:*

`class Solution:`

def buildTree(self, P: List[int], I: List[int]) -> TreeNode:

M = {I[i]: i for i in range(len(I))}

return self.splitTree(P, I, M, 0, 0, len(P)-1)

def splitTree(self, P: List[int], I: List[int], M: dict, pix: int, ileft: int, iright: int) -> TreeNode:

rval = P[pix]

root, imid = TreeNode(rval), M[rval]

if imid > ileft:

root.left = self.splitTree(P, I, M, pix+1, ileft, imid-1)

if imid < iright:

root.right = self.splitTree(P, I, M, pix+imid-ileft+1, imid+1, iright)

return root

*Explanation:*

For this question, we can take advantage of the order of nodes in the traversals. A preorder traversal is **[node, left, right]** while an inorder traversal is **[left, node, right]**.

We know that the **root** node for a tree is the first element of the preorder array (**P**). We also know that every element to the left of the root element in the inorder array (**I**) is on the left subtree, and everything to the right of the **root** element in **I** is on the right subtree.

Once you do that, your problem has now been reduced to a smaller set. Now you have the inorder and preorder traversal for the left and right subtree and you need to figure them out.

In order to make this work, we just need to pass left and right limits (**ileft, iright**) defining the subarray of the current subtree in **I**, as well as the index (**pix**) of the **root** node of the subtree in **P**.

At this point, we *could* iterate forward through **I** until we found out the location (**imid**) of the **root** node each time, but that would push this solution to **time complexity** of **O(N²)**.

Instead, we can make a preliminary **index map** (**M**) of the values in **I**, so that we can look up the value for **imid** in **O(1) time** in each recursion. This will lower the time complexity to **O(N)** at the cost of a **space complexity** of **O(N)**.

At each recursion, if **imid = ileft**, then there are no nodes to the left, so we shouldn’t call a recursion for that side. The same applies to the right side if **imid = iright**.

*Time Complexity: O(N)**where**N**is the length of**P**and**I**Space Complexity: O(N)**for**M*

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!