# Construct Binary Tree from Inorder and Postorder Traversal

### **Problem Statement:-**

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

**Link:** [https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)

### **Problem Explanation with examples:-**

**Example 1**

```markdown
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Explanation: Given the following tree...
  3
 / \
9  20
  /  \
 15   7
...Return the following tree...
```

**Example 2**

```markdown
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Explanation: Given the following tree in inorder traversal and postorder traversal
 -1
...Return the following tree...
```

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

### Intuition:-

* A binary tree problem again so recursion is obvious.
    
* Inorder traversal gives us the left subtree, root, and right subtree.
    
* Postorder traversal gives us the left subtree, right subtree, and root.
    
* So we can use the last element of postorder as the root.
    
* Then we can find the root in the inorder traversal.
    
* Then we can split the inorder array into left subtree and right subtree from the root.
    
* Keep doing this recursively until we reach the leaf nodes.
    

### Solution:-

* Check if inorder is empty, if so return None.
    
* Pop the last element of postorder and put it in `rootVal`.
    
* Create a TreeNode with `rootVal`.
    
* Find the index of `rootVal` in inorder.
    
* Recursively call buildTree on the right subtree of inorder and postorder, and also slice the inorder array from the root index + 1 to the end.
    
* Recursively call buildTree on the left subtree of inorder and postorder, and also slice the inorder array from the start to the root index.
    
* Return root.
    

### Code:-

JAVA Solution

```java
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        int inOrderIdx = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inOrderIdx = i;
                break;
            }
        }

        int leftSubTreeSize = inOrderIdx - inStart;
        root.left = buildTreeHelper(inorder, postorder, inStart, inOrderIdx - 1, postStart, postStart + leftSubTreeSize - 1);
        root.right = buildTreeHelper(inorder, postorder, inOrderIdx + 1, inEnd, postStart + leftSubTreeSize, postEnd - 1);

        return root;
    }
}
```

Python Solution

```python
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None

        rootVal = postorder.pop()
        root = TreeNode(rootVal)

        inOrder_idx = inorder.index(rootVal)

        root.right = self.buildTree(inorder[inOrder_idx+1:],postorder)
        root.left = self.buildTree(inorder[:inOrder_idx],postorder)

        return root
```

### Complexity Analysis:-

**TIME**:-

Time complexity of the `buildTree` function is **O(n^2)** in the worst-case scenario, where n is the number of elements in the inorder and postorder traversals. This happens when the input binary tree is skewed, and each node has only one child. In such a case, the `inorder.index` method takes O(n) time to find the index of the root node, and this operation is performed for each node of the tree. The `pop` method also takes O(1) time. Therefore, the overall time complexity is **O(n^2)**.

However, in the best-case scenario, the binary tree is balanced, and each node has two children. In this case, the `inorder.index` method is only called once for each node, and the `pop` method is called exactly n times. Therefore, the time complexity is **O(n)**.

**SPACE**:-

Space complexity of the `buildTree` function is **O(n)** in the worst-case scenario. This happens when the input binary tree is skewed, and the recursive function calls accumulate on the call stack. In the best-case scenario, the binary tree is balanced, and the height of the call stack is logarithmic to the number of elements in the tree, resulting in a space complexity of O(log n).

### References:-

* [**Recursion**](https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/)
    
* [**Binary Tree**](https://www.geeksforgeeks.org/binary-tree-data-structure/)
    
* [**Tree Traversals**](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)