# Construct Binary Tree from Preorder and Inorder Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/construct-binary-tree-from-preorder-and-inorder-traversal
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Hash Table, Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla)
---
## 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 1:**

![](https://assets.glich.co/dsa/construct-binary-tree-from-preorder-and-inorder-traversal/image0.jpg) 

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

# Approaches
## Brute-Force Recursion with Array Slicing
This approach directly translates the properties of preorder and inorder traversals into a recursive algorithm. The first element of the `preorder` array is the root. We find this root in the `inorder` array to determine the elements of the left and right subtrees. Then, we create new subarrays for the preorder and inorder traversals of the left and right subtrees and make recursive calls.
**Time:** O(N^2) · **Space:** O(N^2)
**Pros:** Conceptually simple and easy to understand.; Directly follows the definition of the traversals.
**Cons:** Highly inefficient in both time and space due to the creation of new array copies in every recursive call.; The repeated linear scan to find the root's index in the inorder array makes it slow for large inputs.
### Explanation
The core idea is to use recursion. The base case for the recursion is when the input arrays are empty, in which case we return `null`.

In each recursive step:
1. Pick the first element from the `preorder` array. This is the root of the current subtree.
2. Create a new `TreeNode` with this value.
3. Search for this root's value in the `inorder` array. Let's say its index is `k`.
4. All elements in the `inorder` array to the left of `k` (from index 0 to `k-1`) belong to the left subtree.
5. All elements in the `inorder` array to the right of `k` (from index `k+1` to the end) belong to the right subtree.
6. The number of elements in the left subtree is `k`.
7. The next `k` elements in the `preorder` array (after the root) belong to the left subtree's preorder traversal. The rest belong to the right subtree's preorder traversal.
8. Create new subarrays for the left and right subtrees' traversals (`left_inorder`, `right_inorder`, `left_preorder`, `right_preorder`).
9. Recursively call the function to build the left and right children.

This process is simple to understand but inefficient due to the repeated creation of new arrays and linear scanning in each recursive call.

```java
import java.util.Arrays;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }

        // The first element of preorder is the root
        TreeNode root = new TreeNode(preorder[0]);

        // Find the root in the inorder array
        int mid = -1;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                mid = i;
                break;
            }
        }

        // Create subarrays for left and right subtrees
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, mid);
        int[] rightInorder = Arrays.copyOfRange(inorder, mid + 1, inorder.length);
        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, mid + 1);
        int[] rightPreorder = Arrays.copyOfRange(preorder, mid + 1, preorder.length);

        // Recursively build the left and right subtrees
        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);

        return root;
    }
}
```
### Algorithm
- If the `preorder` array is empty, return `null`.
- The first element of the `preorder` array, `preorder[0]`, is the root of the tree. Create a `TreeNode` for this root.
- Find the index, `mid`, of the root's value in the `inorder` array. This is a linear scan.
- The elements to the left of `mid` in the `inorder` array form the left subtree. The elements to the right form the right subtree.
- The number of nodes in the left subtree is `mid`.
- Create new subarrays for the left and right subtrees:
  - `left_inorder`: `inorder` from index `0` to `mid - 1`.
  - `right_inorder`: `inorder` from index `mid + 1` to the end.
  - `left_preorder`: `preorder` from index `1` to `mid`.
  - `right_preorder`: `preorder` from index `mid + 1` to the end.
- Recursively call the function to build the left child: `root.left = buildTree(left_preorder, left_inorder)`.
- Recursively call the function to build the right child: `root.right = buildTree(right_preorder, right_inorder)`.
- Return the `root` node.

## Recursion with Pointers/Indices
This approach improves upon the brute-force method by avoiding the creation of new arrays. Instead of slicing arrays, we pass pointers or indices to a helper function. These indices define the current boundaries of the `preorder` and `inorder` subarrays we are considering, which significantly reduces space overhead.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** More space-efficient than the brute-force approach as it avoids creating new arrays.; Reduces memory allocation overhead.
**Cons:** The time complexity is still quadratic in the worst case due to the repeated linear search for the root's index in the `inorder` array.
### Explanation
We define a recursive helper function, say `build(inStart, inEnd)`, which constructs a tree from `preorder` and a specific segment of `inorder` defined by `inStart` and `inEnd`.

A global or class-level variable, `preorderIndex`, is used to keep track of the current root in the `preorder` array. It's initialized to 0 and incremented each time a node is processed.

The algorithm for the helper function `build(inStart, inEnd)` is as follows:
1. Base case: If `inStart > inEnd`, it means the current subarray is empty, so return `null`.
2. Get the current root's value from `preorder[preorderIndex]` and increment `preorderIndex`.
3. Create a new `TreeNode` with this value.
4. Find the index of this root's value within the current `inorder` segment (`inorder[inStart...inEnd]`). This search is a linear scan.
5. Recursively call `build` for the left and right subtrees using the calculated boundaries.

This approach eliminates the space and time overhead of array copying, but the time complexity is still dominated by the linear search in each step.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val; }
 * }
 */
class Solution {
    int preorderIndex;
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        this.preorderIndex = 0;
        return build(0, inorder.length - 1);
    }

    private TreeNode build(int inStart, int inEnd) {
        // Base case
        if (inStart > inEnd) {
            return null;
        }

        // Get current root from preorder and advance index
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        // Find root's index in the current inorder segment
        int inRootIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inRootIndex = i;
                break;
            }
        }

        // Recursively build left and right subtrees
        // Important: Build left subtree first because preorderIndex is advanced sequentially
        root.left = build(inStart, inRootIndex - 1);
        root.right = build(inRootIndex + 1, inEnd);

        return root;
    }
}
```
### Algorithm
- Initialize a global `preorderIndex = 0` to track the current root in the `preorder` array.
- Call a recursive helper function `build(inStart, inEnd)` with initial bounds `0` and `inorder.length - 1`.
- **Inside `build(inStart, inEnd)`:**
  - If `inStart > inEnd`, return `null` (base case).
  - Get the current root's value: `rootVal = preorder[preorderIndex]`, and then increment `preorderIndex`.
  - Create a new `TreeNode` for the root.
  - Linearly scan the `inorder` array from `inStart` to `inEnd` to find the index `inRootIndex` of `rootVal`.
  - The left child is built by the recursive call `build(inStart, inRootIndex - 1)`.
  - The right child is built by the recursive call `build(inRootIndex + 1, inEnd)`.
  - Return the created `root` node.

## Optimized Recursion with HashMap
This is the most efficient approach. It builds upon the previous recursive approach but optimizes the process of finding the root's index in the `inorder` array. By pre-processing the `inorder` array into a `HashMap` that maps each value to its index, we can find the root's index in `O(1)` time, which reduces the overall time complexity to linear.
**Time:** O(N) · **Space:** O(N)
**Pros:** Optimal time complexity of O(N).; Efficiently solves the problem by removing the repetitive search bottleneck.
**Cons:** Requires extra space for the HashMap, which might be a concern for very strict memory constraints.
### Explanation
The overall recursive structure is the same as the previous approach, using indices to define subarrays. The key improvement is the elimination of the linear search.

The algorithm is as follows:
1. First, create a `HashMap` to store the indices of elements in the `inorder` array. This takes `O(N)` time.
2. Initialize a global or class-level variable, `preorderIndex`, to 0.
3. Call a recursive helper function, `build(inStart, inEnd)`, with the initial boundaries of the `inorder` array.
4. Inside the helper function, get the current root from `preorder`, create the node, and then use the `HashMap` to find its position in the `inorder` segment in `O(1)` time.
5. Recursively build the left and right subtrees.

By replacing the `O(N)` search with an `O(1)` lookup, the work done at each node becomes constant, leading to an overall linear time complexity.

```java
import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val; }
 * }
 */
class Solution {
    int preorderIndex;
    Map<Integer, Integer> inorderMap;
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.preorderIndex = 0;
        // Build a hashmap to store value -> index relations
        this.inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(0, inorder.length - 1);
    }

    private TreeNode build(int inStart, int inEnd) {
        // Base case
        if (inStart > inEnd) {
            return null;
        }

        // Get current root from preorder and advance index
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        // Find root's index in inorder using the map (O(1) lookup)
        int inRootIndex = inorderMap.get(rootVal);

        // Recursively build left and right subtrees
        // Important: Build left subtree first because preorderIndex is advanced sequentially
        root.left = build(inStart, inRootIndex - 1);
        root.right = build(inRootIndex + 1, inEnd);

        return root;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` called `inorderMap` to store `(value, index)` pairs from the `inorder` array. This takes `O(N)` time.
- Initialize a global `preorderIndex = 0`.
- Call a recursive helper `build(inStart, inEnd)` with initial bounds `0` and `inorder.length - 1`.
- **Inside `build(inStart, inEnd)`:**
  - If `inStart > inEnd`, return `null`.
  - Get `rootVal = preorder[preorderIndex]` and increment `preorderIndex`.
  - Create a `root` node with `rootVal`.
  - Get the root's index `inRootIndex` from the `inorderMap` in `O(1)` time: `inRootIndex = inorderMap.get(rootVal)`.
  - Set `root.left = build(inStart, inRootIndex - 1)`.
  - Set `root.right = build(inRootIndex + 1, inEnd)`.
  - Return `root`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int [] preorder ; private Map < Integer , Integer > d = new HashMap <>(); public TreeNode buildTree ( int [] preorder , int [] inorder ) { int n = preorder . length ; this . preorder = preorder ; for ( int i = 0 ; i < n ; ++ i ) { d . put ( inorder [ i ], i ); } return dfs ( 0 , 0 , n ); } private TreeNode dfs ( int i , int j , int n ) { if ( n <= 0 ) { return null ; } int v = preorder [ i ]; int k = d . get ( v ); TreeNode l = dfs ( i + 1 , j , k - j ); TreeNode r = dfs ( i + 1 + k - j , k + 1 , n - 1 - ( k - j )); return new TreeNode ( v , l , r ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */ var buildTree =
  function (preorder, inorder) {
    const d = new Map();
    const n = inorder.length;
    for (let i = 0; i < n; ++i) {
      d.set(inorder[i], i);
    }
    const dfs = (i, j, n) => {
      if (n <= 0) {
        return null;
      }
      const v = preorder[i];
      const k = d.get(v);
      const l = dfs(i + 1, j, k - j);
      const r = dfs(i + 1 + k - j, k + 1, n - 1 - (k - j));
      return new TreeNode(v, l, r);
    };
    return dfs(0, 0, n);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * buildTree ( vector < int >& preorder , vector < int >& inorder ) { int n = preorder . size (); unordered_map < int , int > d ; for ( int i = 0 ; i < n ; ++ i ) { d [ inorder [ i ]] = i ; } function < TreeNode * ( int , int , int ) > dfs = [ & ]( int i , int j , int n ) -> TreeNode * { if ( n <= 0 ) { return nullptr ; } int v = preorder [ i ]; int k = d [ v ]; TreeNode * l = dfs ( i + 1 , j , k - j ); TreeNode * r = dfs ( i + 1 + k - j , k + 1 , n - 1 - ( k - j )); return new TreeNode ( v , l , r ); }; return dfs ( 0 , 0 , n ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right # best class Solution : def buildTree ( self , preorder : List [ int ], inorder : List [ int ]) -> Optional [ TreeNode ]: if not preorder : # or, not inorder return None v = preorder [ 0 ] i = inorder . index ( v ) root = TreeNode ( v ) root . left = self . buildTree ( preorder [ 1 : i + 1 ], inorder [: i ]) root . right = self . buildTree ( preorder [ i + 1 :], inorder [ i + 1 :]) return root # inorder.index(preorder_val) class Solution : def buildTree ( self , preorder : List [ int ], inorder : List [ int ]) -> Optional [ TreeNode ]: def dfs ( pleft , pright , ileft , iright ): if pleft > pright or ileft > iright : return None k = inorder . index ( preorder [ pleft ]) root = TreeNode ( preorder [ pleft ]) root . left = dfs ( pleft + 1 , pleft + ( k - ileft ), ileft , k - 1 ) root . right = dfs ( pleft + 1 + ( k - ileft ), pright , k + 1 , iright ) return root n = len ( preorder ) return dfs ( 0 , n - 1 , 0 , n - 1 ) # build dict for val => index class Solution : def buildTree ( self , preorder : List [ int ], inorder : List [ int ]) -> Optional [ TreeNode ]: def dfs ( pleft , pright , ileft , iright ): if pleft > pright or ileft > iright : return None v = preorder [ pleft ] k = d [ v ] root = TreeNode ( v ) root . left = dfs ( pleft + 1 , pleft + ( k - ileft ), ileft , k - 1 ) root . right = dfs ( pleft + 1 + ( k - ileft ), pright , k + 1 , iright ) return root d = { v : i for i , v in enumerate ( inorder )} n = len ( preorder ) return dfs ( 0 , n - 1 , 0 , n - 1 ) ############ ''' search for index, also use .index(val) >>> a = [1,2,3,4,5] >>> a.index(3) 2 ''' class Solution ( object ): def buildTree ( self , preorder , inorder ): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ self . preindex = 0 ind = { v : i for i , v in enumerate ( inorder )} head = self . dc ( 0 , len ( preorder ) - 1 , preorder , inorder , ind ) return head def dc ( self , start , end , preorder , inorder , ind ): if start <= end : mid = ind [ preorder [ self . preindex ]] self . preindex += 1 root = TreeNode ( inorder [ mid ]) root . left = self . dc ( start , mid - 1 , preorder , inorder , ind ) root . right = self . dc ( mid + 1 , end , preorder , inorder , ind ) return root ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def buildTree ( self , preorder : List [ int ], inorder : List [ int ]) -> Optional [ TreeNode ]: def dfs ( i : int , j : int , n : int ): if n <= 0 : return None v = preorder [ i ] k = d [ v ] l = dfs ( i + 1 , j , k - j ) r = dfs ( i + 1 + k - j , k + 1 , n - k + j - 1 ) return TreeNode ( v , l , r ) d = { v : i for i , v in enumerate ( inorder )} return dfs ( 0 , 0 , len ( preorder ))
```