# Construct Binary Tree from Inorder and Postorder Traversal

## Leetcode Daily Challenge (16th March, 2023)

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

**Problem Explanation with examples:-**

**Example 1**

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

```
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

```
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

```
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).