Solution: Construct Binary Tree from Preorder and Inorder Traversal
Tags: algorithms, javascript, java, python
Published: 2021-06-08 17:28:35

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/1258712).*

---

#### [Leetcode Problem #105 (*Medium*): Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

---

#### ***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 1 Visual](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg)
>
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.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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.

![Visual 1](https://i.imgur.com/qZZqFyY.gif)

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```