Construct Binary Tree from Inorder and Postorder Traversal

Intuition

Postorder visits the root last, so the final unused postorder value is the root of the current subtree. Just as with the preorder/inorder pairing, the root's position in inorder separates the left subtree from the right subtree. Because we consume postorder from its end and postorder lists the right subtree immediately before the root, we must build the right subtree before the left one. A hash map from value to inorder index gives O(1) root positioning, and a single backward-moving postorder pointer hands out roots in the correct order.

Algorithm walkthrough

1. 1Map every inorder value to its index and set a postorder pointer at the last position.
2. 2Define a recursive helper that takes the inorder bounds [left, right] of the current subtree.
3. 3Return null when left is greater than right.
4. 4Read the value at the postorder pointer as the root and decrement the pointer, then find its inorder index mid.
5. 5Build the right subtree from [mid + 1, right] first, then the left subtree from [left, mid - 1], mirroring the reverse consumption of postorder.
6. 6Return the root; start the recursion over the full inorder range.

Implementation

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(inorder)}
        self.post = len(postorder) - 1

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            root_val = postorder[self.post]
            self.post -= 1
            root = TreeNode(root_val)
            mid = idx[root_val]
            root.right = build(mid + 1, right)
            root.left = build(left, mid - 1)
            return root

        return build(0, len(inorder) - 1)