Follow

# Leeting-LCS

Follow # Construct Binary Tree from Inorder and Postorder Traversal

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

Lakshit Chiranjiv Sagar
·Mar 16, 2023·

• Problem Statement:-
• Problem Explanation with examples:-
• Intuition:-
• Solution:-
• Code:-
• Complexity Analysis:-
• References:-
• Connect with me:-

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

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