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: the root is 3 (last of postorder). In inorder, all remaining values
        sit LEFT of 3, so 3 has only a left subtree. Recursing gives the
        left-leaning chain:

            3
           /
          2
         /
        1

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

Hint 1

Which single node's identity can you read off immediately from the `postorder` array?

Hint 2

Once you know the root, find it in `inorder`. That index splits `inorder` into the exact left-subtree values and right-subtree values — and the left subtree's *size* tells you how to split `postorder` too.

Hint 3

Recurse: build the root from the end of `postorder`, then recursively build right and left subtrees. To reach `O(n)`, precompute a value→index hash map for `inorder` and consume `postorder` from the back (build the **right** subtree before the left).

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 last element of postorder is the root. 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


def buildTree(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 = buildTree(inorder[:mid], postorder[:mid])
    root.right = 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 passes, but a skewed input reaches roughly 4.5M operations plus heavy copying.

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

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


def buildTree(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]):

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

graph TD
    A["3"] --> B["9"]
    A --> C["20"]
    C --> D["15"]
    C --> E["7"]

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)

Postorder is left, right, root, so reading it backwards yields root, right, left. If you build the right subtree before the left, you can pop values off the end of postorder one at a time, with no explicit postorder ranges. 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


def buildTree(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, do not build the left subtree first. The back of postorder serves roots in root, right, left order, so recursing left first attaches the 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.