Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversals of a binary tree, reconstruct the original tree and return its root.

Function signature

func BuildTree(inorder []int, postorder []int) *TreeNode

Inputs / outputs

• inorder: inorder traversal (left, root, right).
• postorder: postorder traversal (left, right, root).
• Return: root of the reconstructed tree.

Example

inorder   = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Output: tree with root 3

Constraints

• 0 <= len(inorder) == len(postorder) <= 100_000
• All values are unique.

Core idea (near-solution)

The last element in postorder is the root. Split inorder around that root to get left and right subtrees, then recurse. Build the right subtree first because postorder is consumed from the end.

Invariant: the current recursion builds exactly the subtree described by inorder[lo:hi] and the current postorder index.

Algorithm (step-by-step)

1. Build a map from value to its index in inorder.
2. Set postIdx = len(postorder) - 1.
3. Recursive build(lo, hi):
   • If lo > hi, return nil.
   • rootVal = postorder[postIdx], decrement postIdx.
   • Find mid = inorderIndex[rootVal].
   • Create root node.
   • Recurse right with build(mid+1, hi).
   • Recurse left with build(lo, mid-1).
4. Return the root.

Correctness sketch

• Invariant: the current recursion builds exactly the subtree described by inorder[lo:hi] and the current postorder index.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

Trace (hand walkthrough)

Example input:
inorder   = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Output: tree with root 3

Walk:
- postorder last=3 -> root=3; inorder split [9] |3| [15,20,7]
- right subtree root=20 (next from postorder); split [15]|20|[7]
- left subtree from inorder [9] -> node 9

Pitfalls to avoid

• Building the left subtree before the right (consumes wrong postorder elements).
• Scanning inorder each time instead of using a map (O(n^2)).
• Off-by-one errors in the subtree bounds.

Complexity

• Time: O(n).
• Extra space: O(n) for the index map and recursion stack.

Implementation notes (Go)

• Use a package-level postIdx or pass by pointer for efficient decrementing.
• TreeNode values are unique, so the index map is safe.