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