# Construct Binary Tree from Inorder and Postorder Traversal

###
Shoryu
*Updated on *
・1 min read

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

## Problems

Construct Binary Tree from Inorder and Postorder Traversal

We want to return the binary tree by given inorder and postorder Traversal.

## Approach

Postorder is `left->right->root`

and inorder is `left->root->right`

, so the root of tree is the rightmost of postorder traversal and we can get to know the subtree of it by checking inorder traversal.

For example:

inorder = 9,3,15,20,7 (left->root->right)

postorder = 9,15,7,20,3 (left->right->root)

The root is `3`

because it is the rightmost in postorder traversal and the left subtree is `9`

and the right subtree is `15, 20, 7`

because in inorder Traversal, `9`

is left of `3`

(=root) and `15, 20, 7`

is right of `3`

. The next root is 20, and the right subtree is `15`

and the left subtree is `7`

.

So we are able to solve this question by repeating this process.

## Solution

```
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def helper(left_end, right_end):
if left_end > right_end:
return None
value = postorder.pop()
root = TreeNode(value)
index = index_map[value]
root.right = helper(index + 1, right_end)
root.left = helper(left_end, index - 1)
return root
index_map = {val:idx for idx, val in enumerate(inorder)}
return helper(0, len(inorder) - 1)
```

Thank you for reading this article!

I always welcome your feedback, question, and idea.