Construct Binary Tree from Inorder and Postorder Traversal

shoryu profile image 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!


Construct Binary Tree from Inorder and Postorder Traversal

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


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.


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.

Posted on by:

shoryu profile



I'm an iOS Developer at a startup company. I'm learning about algorithms and data structures in Python.


Editor guide