*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #105 (*Medium*): Construct Binary Tree from Preorder and Inorder Traversal

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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 returnthe binary tree.

####
*Examples:*

*Examples:*

Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Visual:

Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]

####
*Constraints:*

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

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

For this solution, we can take advantage of the order of nodes in the **preorder** and **inorder** 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.

Since we know the length of the left and right subtrees by finding the **root** in **I**, and since we know the order of the left and right subtrees in **P**, we can use that to determine the location of the **root** node in **P** for each of the two subtrees.

With this information, we can define a **recursive** helper function (**splitTree**) that will split the tree into two and then recursively do the same for each subtree.

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 a **time complexity** of **O(N^2)**.

Instead, we can make a prelimanary **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)**.

In the example in the graphic above, where **P = [8,2,7,1,9,3,6]** and **I = [7,2,1,8,3,9,6]**, the **root** would be **8**, so we know that **imid** (its location in **I**) is **3**, and since we still are using the full array, **ileft = 0** and **iright = I.length-1**, or **6**. This means that the left subtree is **imid - ileft = 3** elements long (**[7,2,1]** to the left of **8** in **I**) and the right subtree is **iright - imid = 3** elements long (**[3,9,6]** to the right of **8** in **I**).

We can apply those dimensions from **I** to figure out the ranges of those subtrees in **P**, as well. The left subtree will start right after the **root** in **P** (**pix + 1**), and the right subtree will start once the left subtree ends (**pix + 1 + (imid - ileft)**.

At each recursion, if **imid = ileft**, then there are no nodes in the left subtree, 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**

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var buildTree = function(P, I) {
let M = new Map()
for (let i = 0; i < I.length; i++)
M.set(I[i], i)
return splitTree(P, M, 0, 0, I.length-1)
};
var splitTree = function(P, M, pix, ileft, iright) {
let rval = P[pix],
root = new TreeNode(rval),
imid = M.get(rval)
if (imid > ileft)
root.left = splitTree(P, M, pix+1, ileft, imid-1)
if (imid < iright)
root.right = splitTree(P, M, pix+imid-ileft+1, imid+1, iright)
return root
}
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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, M, 0, 0, len(P)-1)
def splitTree(self, P: 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, M, pix+1, ileft, imid-1)
if imid < iright:
root.right = self.splitTree(P, M, pix+imid-ileft+1, imid+1, iright)
return root
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public TreeNode buildTree(int[] P, int[] I) {
Map<Integer, Integer> M = new HashMap<>();
for (int i = 0; i < I.length; i++)
M.put(I[i], i);
return splitTree(P, M, 0, 0, I.length-1);
}
private TreeNode splitTree(int[] P, Map<Integer, Integer> M, int pix, int ileft, int iright) {
int rval = P[pix], imid = M.get(rval);
TreeNode root = new TreeNode(rval);
if (imid > ileft)
root.left = splitTree(P, M, pix+1, ileft, imid-1);
if (imid < iright)
root.right = splitTree(P, M, pix+imid-ileft+1, imid+1, iright);
return root;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
TreeNode* buildTree(vector<int>& P, vector<int>& I) {
unordered_map<int, int> M;
for (int i = 0; i < I.size(); i++)
M[I[i]] = i;
return splitTree(P, M, 0, 0, I.size()-1);
}
private:
TreeNode* splitTree(vector<int>& P, unordered_map<int, int>& M, int pix, int ileft, int iright) {
int rval = P[pix], imid = M[rval];
TreeNode* root = new TreeNode(rval);
if (imid > ileft)
root->left = splitTree(P, M, pix+1, ileft, imid-1);
if (imid < iright)
root->right = splitTree(P, M, pix+imid-ileft+1, imid+1, iright);
return root;
}
};
```

## Top comments (0)