Construct Binary Tree from Inorder and Postorder Traversal

Problem

You are given two integer arrays describing the same binary tree: inorder (the sequence of node values from an inorder traversal) and postorder (the sequence from a postorder traversal). All node values are distinct. Rebuild the tree and return its root.

Recall the traversal orders: inorder visits left subtree, node, right subtree; postorder visits left subtree, right subtree, node.

Examples

Example 1

Input:  inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: the tree

        3
       / \
      9   20
         /  \
        15   7

The last postorder value (3) is the root; everything left of 3 in inorder ([9]) is the left subtree, everything right ([15, 20, 7]) is the right subtree.

Example 2

Input:  inorder = [-1], postorder = [-1]
Output: a single node with value -1

One value gives a one-node tree.

Example 3

Input:  inorder = [1, 2, 3], postorder = [1, 2, 3]
Output: a right-leaning chain 3 → 2 → 1? No — check: root is 3 (last of postorder);
        in inorder everything is LEFT of 3, so 3 has only a left subtree:
        3 ← 2 ← 1 (each node is its parent's left child)

The split position in inorder decides which side each element belongs to.

Constraints

• 1 <= inorder.length <= 3000, postorder.length == inorder.length
• -3000 <= values <= 3000, all values distinct (this is what makes the split unambiguous)
• Both arrays are guaranteed to be valid traversals of the same tree.
• Expected complexity: O(n) time is achievable; O(n^2) passes but is the naive version.

Think about it first

TL;DR

Recursive divide & conquer: last postorder element = root, split inorder around it; with a hash map of inorder indices it runs in O(n) time, O(n) space.

Approach 1 — Brute force: slice and recurse

The naive intuition: the last element of postorder is the root. Linearly search for it in inorder; everything to its left is the left subtree, everything to its right is the right subtree. Slice both arrays accordingly and recurse.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        root_val = postorder[-1]
        root = TreeNode(root_val)
        mid = inorder.index(root_val)          # O(n) search
        root.left = self.buildTree(inorder[:mid], postorder[:mid])
        root.right = self.buildTree(inorder[mid + 1:], postorder[mid:-1])
        return root

Complexity: O(n^2) time in the worst case (a skewed tree makes each level’s index search and slices cost O(n)), O(n^2) space from the slices. With n <= 3000 this actually passes, but a skewed input pushes ~4.5M operations plus heavy copying — and the interviewer will ask for better.

Approach 2 — Hash map + index arithmetic (no slicing)

The insight: two costs make Approach 1 quadratic — the linear index search and the array slicing. Both disappear if you (a) precompute a value→index map over inorder, and (b) recurse on index ranges instead of copied subarrays. The left subtree has mid - lo nodes, which tells you exactly where the postorder range splits.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


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

        def build(in_lo: int, in_hi: int, post_lo: int, post_hi: int) -> Optional[TreeNode]:
            # ranges are inclusive
            if in_lo > in_hi:
                return None
            root_val = postorder[post_hi]
            root = TreeNode(root_val)
            mid = idx[root_val]
            left_size = mid - in_lo
            root.left = build(in_lo, mid - 1, post_lo, post_lo + left_size - 1)
            root.right = build(mid + 1, in_hi, post_lo + left_size, post_hi - 1)
            return root

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

Walkthrough on Example 1 (inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]):

1. build(0,4, 0,4): root = postorder[4] = 3, mid = 1, left_size = 1.
2. Left: build(0,0, 0,0) → root = postorder[0] = 9, both children empty → leaf 9.
3. Right: build(2,4, 1,3) → root = postorder[3] = 20, mid = 3, left_size = 1.
4. Its left: build(2,2, 1,1) → leaf 15. Its right: build(4,4, 2,2) → leaf 7.
5. Assembled: 3(9, 20(15, 7)) — matches the expected tree.

Complexity: O(n) time — each node is built once with O(1) work; O(n) space for the map plus O(h) recursion stack (h = tree height, up to n).

Approach 3 — Consume postorder from the back (elegant variant)

The insight: postorder is left, right, root, so reading it backwards yields root, right, left. If you build the right subtree before the left, you can just pop values off the end of postorder one at a time — no explicit postorder ranges at all. Only the inorder boundary is needed to know when a subtree is exhausted.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


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

        def build(in_lo: int, in_hi: int) -> Optional[TreeNode]:
            if in_lo > in_hi:
                return None
            root_val = postorder.pop()          # next root, from the back
            root = TreeNode(root_val)
            mid = idx[root_val]
            root.right = build(mid + 1, in_hi)  # right FIRST — order matters
            root.left = build(in_lo, mid - 1)
            return root

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

Walkthrough on Example 1: pop 3 (root, mid=1) → build right over inorder [2..4]: pop 20 (mid=3) → its right over [4..4]: pop 7 → its left over [2..2]: pop 15 → back up; build 3’s left over [0..0]: pop 9. Pops in order 3, 20, 7, 15, 9 — exactly reversed postorder.

Complexity: O(n) time, O(n) space (map + recursion stack). Same asymptotics as Approach 2, less bookkeeping.

Common pitfalls

• In Approach 3, building the left subtree first — the back of postorder serves roots in root, right, left order, so recursing left first attaches wrong values.
• Off-by-one when splitting postorder in Approach 2: the right subtree ends at post_hi - 1 (excluding the root), not post_hi.
• Mutating a shared postorder while also passing slices — pick one strategy (indices or pops), not both.
• Assuming this works with duplicate values — the inorder split is ambiguous unless values are distinct (which the constraints guarantee).

Pattern takeaway

Tree-from-traversals problems all follow one recipe: one traversal hands you the root at a known position (front of preorder, back of postorder), and the inorder array splits the remaining values into left/right subtrees at the root’s index. Memorize the two upgrades that make it linear — a value→index hash map, and recursing on index ranges (or consuming the root-supplying array in its natural order) instead of slicing.