# Construct Binary Tree from Inorder and Postorder Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/construct-binary-tree-from-inorder-and-postorder-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)
---
## Problem
Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return _the binary tree_.

**Example 1:**

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

**Input:** inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
**Output:** [3,9,20,null,null,15,7]

**Example 2:**

**Input:** inorder = [-1], postorder = [-1]
**Output:** [-1]

**Constraints:**

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

# Approaches
## Recursive Approach with Linear Search
This approach uses a straightforward recursive strategy. The core idea relies on the properties of postorder and inorder traversals. The last element in a postorder traversal is the root of the tree. Once the root is identified, we can find its position in the inorder traversal. All elements to the left of the root in the inorder traversal belong to the left subtree, and all elements to the right belong to the right subtree. This allows us to partition the problem and recursively build the left and right subtrees. The main drawback is the need to perform a linear scan of the `inorder` array in each recursive step to find the root's index, which leads to a quadratic time complexity in the worst case.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Relatively simple to understand and implement.; Follows the definition of traversals directly.
**Cons:** The time complexity of O(N^2) is inefficient for large inputs.; Repeatedly scanning the inorder array is a redundant operation.
### Explanation
The algorithm is implemented using a recursive helper function that takes the start and end indices for the current segments of the `inorder` and `postorder` arrays. In each call, we first identify the root from the end of the `postorder` segment. Then, we iterate through the `inorder` segment to locate this root. This location tells us the boundary between the left and right subtrees. We can also determine the size of the left subtree, which helps in partitioning the `postorder` array for the subsequent recursive calls. The function then recursively calls itself to build the left and right children and connects them to the root.

```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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length == 0) {
            return null;
        }
        return buildHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode buildHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        // Base case: if the subarray is empty
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        // The last element in the current postorder segment is the root
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

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

        // Calculate the size of the left subtree
        int leftSubtreeSize = rootIndex - inStart;

        // Recursively build the left subtree
        root.left = buildHelper(inorder, inStart, rootIndex - 1, 
                                postorder, postStart, postStart + leftSubtreeSize - 1);
        
        // Recursively build the right subtree
        root.right = buildHelper(inorder, rootIndex + 1, inEnd, 
                                 postorder, postStart + leftSubtreeSize, postEnd - 1);

        return root;
    }
}
```
### Algorithm
1. The main function `buildTree` initializes the process by calling a recursive helper function with the full range of both `inorder` and `postorder` arrays.
2. The recursive helper function `buildHelper(inorder, inStart, inEnd, postorder, postStart, postEnd)` works on the subarrays defined by the start and end indices.
3. **Base Case:** If the start index is greater than the end index for either array, it means the subarray is empty, and we return `null`.
4. **Identify Root:** The root of the current subtree is always the last element of the current `postorder` subarray (`postorder[postEnd]`). A new `TreeNode` is created with this value.
5. **Find Root in Inorder:** A linear search is performed on the current `inorder` subarray (from `inStart` to `inEnd`) to find the index of the root's value. Let's call this `rootIndex`.
6. **Partition Subtrees:**
   - The elements to the left of `rootIndex` in the `inorder` array (`inStart` to `rootIndex - 1`) belong to the left subtree.
   - The elements to the right of `rootIndex` (`rootIndex + 1` to `inEnd`) belong to the right subtree.
7. **Calculate Left Subtree Size:** The number of nodes in the left subtree is calculated as `leftSubtreeSize = rootIndex - inStart`.
8. **Recursive Calls:**
   - The left child is constructed by a recursive call with the corresponding `inorder` and `postorder` subarrays for the left subtree.
   - The right child is constructed similarly with the subarrays for the right subtree.
9. **Return Node:** The constructed node with its left and right children attached is returned.

## Optimized Recursive Approach with HashMap
This approach optimizes the previous one by eliminating the repeated linear search. The bottleneck of finding the root's index in the `inorder` array is resolved by pre-processing the `inorder` array into a `HashMap`. This map stores each node's value and its index, allowing for an O(1) lookup. The recursion proceeds by using a single pointer, `postIndex`, to iterate backward through the `postorder` array. Since `postorder` is `[Left, Right, Root]`, traversing it backward gives us the root, then the root of the right subtree, then the root of the left subtree. This dictates that we must recursively build the right subtree first, then the left. This optimization reduces the time complexity from O(N^2) to a much more efficient O(N).
**Time:** O(N) · **Space:** O(N)
**Pros:** Optimal time complexity of O(N).; Efficiently constructs the tree by visiting each node only once.; Avoids creating new array copies in each recursive call by using indices.
**Cons:** Requires O(N) extra space for the HashMap.
### Explanation
The core of this optimized solution is a `HashMap` that maps each value in the `inorder` array to its index. This map is built once at the beginning. A global index, `postIndex`, is initialized to the end of the `postorder` array. The recursive function then does the following: it pops the last element from `postorder` (by using `postorder[postIndex--]`) to get the current root, creates the node, looks up its index in the `inorder` map to find the partition point, and then recursively builds the right and left subtrees. The key insight is the order of recursion: since the element before the root in a reversed `postorder` traversal is the root of the right subtree, the recursive call for the right child must be made before the call for the left child.

```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 {
    int postIndex;
    Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length == 0) {
            return null;
        }

        // Start from the end of postorder, which is the root
        postIndex = postorder.length - 1;
        
        // Build a map for O(1) lookup of inorder indices
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return buildHelper(0, inorder.length - 1);
    }

    private TreeNode buildHelper(int inStart, int inEnd) {
        // Base case: no elements to construct the tree
        if (inStart > inEnd) {
            return null;
        }

        // Get the current root value from postorder and move the index
        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);

        // Get the index of the root from the inorder map
        int rootIndex = inorderMap.get(rootVal);

        // IMPORTANT: Build the right subtree first because we are traversing
        // postorder from right to left.
        root.right = buildHelper(rootIndex + 1, inEnd);
        
        // Then build the left subtree
        root.left = buildHelper(inStart, rootIndex - 1);

        return root;
    }
}
```
### Algorithm
1. **Pre-computation:** Create a `HashMap` to store the values of the `inorder` array as keys and their corresponding indices as values. This allows for O(1) lookup of a root's position in the `inorder` array.
2. **Initialization:** Initialize a global or class-level pointer, `postIndex`, to the last index of the `postorder` array (`postorder.length - 1`). This pointer will be used to traverse the `postorder` array from right to left.
3. **Recursive Helper:** Define a recursive helper function, `buildHelper(inStart, inEnd)`, which takes the start and end indices of the current `inorder` segment.
4. **Base Case:** If `inStart > inEnd`, the current segment is empty, so return `null`.
5. **Identify and Process Root:**
   - The value of the current root is `postorder[postIndex]`.
   - Create a new `TreeNode` with this value.
   - Decrement `postIndex` to move to the root of the next subtree in the `postorder` sequence.
6. **Find Root in Inorder:** Use the pre-computed `HashMap` to find the index of the root in the `inorder` array in O(1) time. Let this be `rootIndex`.
7. **Recursive Calls (Crucial Order):** Because we are processing `postorder` from right to left (which follows a `Root -> Right Subtree -> Left Subtree` pattern), we must build the right subtree *before* the left subtree.
   - **Build Right Subtree:** Make a recursive call `buildHelper(rootIndex + 1, inEnd)` and assign the result to `root.right`.
   - **Build Left Subtree:** After the right subtree is fully constructed, `postIndex` will correctly point to the root of the left subtree. Make a recursive call `buildHelper(inStart, rootIndex - 1)` and assign the result to `root.left`.
8. **Return Root:** Return the constructed `root` node.

# 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 Map < Integer , Integer > indexes = new HashMap <>(); public TreeNode buildTree ( int [] inorder , int [] postorder ) { for ( int i = 0 ; i < inorder . length ; ++ i ) { indexes . put ( inorder [ i ], i ); } return dfs ( inorder , postorder , 0 , 0 , inorder . length ); } private TreeNode dfs ( int [] inorder , int [] postorder , int i , int j , int n ) { if ( n <= 0 ) { return null ; } int v = postorder [ j + n - 1 ]; int k = indexes . get ( v ); TreeNode root = new TreeNode ( v ); root . left = dfs ( inorder , postorder , i , j , k - i ); root . right = dfs ( inorder , postorder , k + 1 , j + k - i , n - k + i - 1 ); return root ; } }
```

### 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: unordered_map < int , int > indexes ; TreeNode * buildTree ( vector < int >& inorder , vector < int >& postorder ) { for ( int i = 0 ; i < inorder . size (); ++ i ) indexes [ inorder [ i ]] = i ; return dfs ( inorder , postorder , 0 , 0 , inorder . size ()); } TreeNode * dfs ( vector < int >& inorder , vector < int >& postorder , int i , int j , int n ) { if ( n <= 0 ) return nullptr ; int v = postorder [ j + n - 1 ]; int k = indexes [ v ]; TreeNode * root = new TreeNode ( v ); root -> left = dfs ( inorder , postorder , i , j , k - i ); root -> right = dfs ( inorder , postorder , k + 1 , j + k - i , n - k + i - 1 ); return root ; } };
```

### 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 class Solution : def buildTree ( self , inorder : List [ int ], postorder : List [ int ]) -> TreeNode : if not postorder : return None v = postorder [ - 1 ] root = TreeNode ( val = v ) i = inorder . index ( v ) root . left = self . buildTree ( inorder [: i ], postorder [: i ]) root . right = self . buildTree ( inorder [ i + 1 :], postorder [ i : - 1 ]) return root ############# # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None ''' search for index, also use .index(val) >>> a = [1,2,3,4,5] >>> a.index(3) 2 ''' class Solution ( object ): def buildTree ( self , inorder , postorder ): """ :type inorder: List[int] :type postorder: List[int] :rtype: TreeNode """ if inorder and postorder : postorder . reverse () self . index = 0 d = {} for i in range ( 0 , len ( inorder )): d [ inorder [ i ]] = i return self . dfs ( inorder , postorder , 0 , len ( postorder ) - 1 , d ) def dfs ( self , inorder , postorder , start , end , d ): if start <= end : root = TreeNode ( postorder [ self . index ]) mid = d [ postorder [ self . index ]] self . index += 1 root . right = self . dfs ( inorder , postorder , mid + 1 , end , d ) root . left = self . dfs ( inorder , postorder , start , mid - 1 , d ) return root
```