Reconstruct tree from inorder and postorder

Given two arrays representing the inorder and postorder traversals of a binary tree with unique values, reconstruct the original binary tree and return its root node. Implement a recursive solution, clearly defining base cases such as empty ranges. Analyze the time and space complexity. If you choose array slicing, explain its impact on complexity; alternatively, implement an index-range approach using a value-to-index map to achieve linear time.

Reconstruct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder representing the inorder and postorder traversals of a binary tree with unique node values, reconstruct the tree and return a level-order serialization of it.

Return the tree as a list produced by a breadth-first (level-order) walk: visit nodes left-to-right level by level, appending each node's value, and appending null/None for each missing child of a visited node. Trim trailing null values. (For example, the tree

    3
   / \
  9  20
     /  \
    15   7

serializes to [3, 9, 20, null, null, 15, 7].)

The last element of postorder is always the root. Locate the root in inorder: everything to its left forms the left subtree, everything to its right forms the right subtree. Recurse, consuming postorder from the back (right subtree before left subtree, since postorder is left-right-root reversed).

Implement a recursive solution with a clear base case for empty ranges. Prefer the index-range + value-to-index map approach for O(n) time over repeated array slicing (which makes the build O(n^2) due to per-call copying and re-searching).

Constraints

• 0 <= len(inorder) == len(postorder)
• All node values are unique
• postorder is a valid postorder traversal of the same tree described by inorder
• Node values fit in a signed 32-bit integer (may be negative)

Examples

Example 1

Input: ([9, 3, 15, 20, 7], [9, 15, 7, 20, 3])
Output: [3, 9, 20, None, None, 15, 7]

Explanation: Classic example: root 3 (last of postorder); 9 is its left child, 20 its right; 20 has children 15 and 7.

Example 2

Input: ([], [])
Output: []

Explanation: Empty traversals reconstruct the empty tree (base case lo > hi at the top level).

Hints

1. The last element of postorder is the root of the (sub)tree. Find it in inorder to split into left and right subtrees.
2. Consume postorder from the back. Because postorder ends with the root and the right subtree's nodes come just before it, build the RIGHT subtree before the LEFT one when popping from the end.
3. Precompute a value-to-index map over inorder so each root lookup is O(1) — this turns the O(n^2) slicing approach into O(n). Use index ranges (lo, hi) instead of copying subarrays.
4. Your base case is an empty range (lo > hi), which returns no node — this naturally handles leaves and the empty tree.