---
link: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
tags: array, tree, bt
---

# 106. Construct Binary Tree from Inorder and Postorder Traversal

## Question
Given inorder and postorder traversal of a tree, construct the binary tree.

**Note:**
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

## Solution: Python

"""
O(n^2) runtime
"""

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return None
        
        root = inorder.index(postorder.pop())
        node = TreeNode(inorder[root])
        node.right= self.buildTree(inorder[root + 1:], postorder)
        node.left = self.buildTree(inorder[:root], postorder)
        
        return node
    
    
    def buildTreeInitialSolution(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None
        
        root = preorder[0]
        root_index = inorder.index(root)
        left_subtree_inorder = inorder[:root_index]
        right_subtree_inorder = inorder[root_index + 1:]
        
        
        right_subtree_index = self.findIndexOfRightSubtreeInPreorder(preorder, root, left_subtree_inorder)
        left_subtree_preorder = preorder[1:right_subtree_index]
        right_subtree_preorder = preorder[right_subtree_index:]
        
        
        node = TreeNode(root)
        node.left = self.buildTree(left_subtree_preorder, left_subtree_inorder)
        node.right = self.buildTree(right_subtree_preorder, right_subtree_inorder)
        
        return node
        
    def findIndexOfRightSubtreeInPreorder(self, preorder, root, left_subtree):
        left_subtree = set(left_subtree)
        
        index = None
                
        for index, el in enumerate(preorder):
            if not (el == root or el in left_subtree):
                return index
                
        return index + 1

## Solution: Java