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.

Why this is worth learning

Reading postorder backward gives root, right, left. The subtree construction order must follow that reversed consumption order.

Before coding: one-minute experiment

For inorder [1,2,3] and postorder [1,3,2], which child subtree must be built first while consuming postorder backward?

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)

Postorder names a subtree's root last, but the preceding values alone do not reveal which belong left or right. Locate that root in inorder to obtain the two subtree sizes, then split the postorder interval by those sizes. Repeatedly scanning inorder can cost O(n²) on a skewed tree; a position map removes those repeated searches when values are unique. The supplied reference passes inclusive ranges in both arrays, so each child owns its interval and may be built in either order. A shared backward postorder cursor is a different representation: it must build right before left because backward order is root, right, left.

Invariant: build(inL,inR,postL,postR) reconstructs exactly the same subtree described by both ranges. Both intervals have equal length; an empty interval returns nil.

Algorithm (step-by-step)

1. Map each value to its inorder index once.
2. Call build(0,n-1,0,n-1). An empty interval returns nil.
3. Select rootVal = postorder[postR], mid = index[rootVal], and leftSize = mid-inL.
4. Build the left child from inorder [inL,mid-1] and postorder [postL,postL+leftSize-1].
5. Build the right child from inorder [mid+1,inR] and postorder [postL+leftSize,postR-1].
6. Return a fresh root connected to those children. The reference builds left first; the disjoint explicit ranges make that safe.

Correctness sketch

For an empty interval there are no nodes, so nil is correct. For a nonempty interval, postorder's last value is its root. Its unique inorder position separates exactly leftSize left-subtree nodes from the right-subtree nodes. Postorder places those left nodes first, then the right nodes, then the root, yielding the two ranges above. Each recursive interval is smaller and describes one complete child subtree. By induction the children are correct; attaching them reconstructs the unique tree. Each value becomes one root, so all nodes are consumed exactly once.

Trace (hand walkthrough)

inorder   = [9,3,15,20,7]
postorder = [9,15,7,20,3]
root: postorder[4]=3; mid=1; leftSize=1
left:  inorder[0..0]=[9], postorder[0..0]=[9] -> leaf 9
right: inorder[2..4]=[15,20,7], postorder[1..3]=[15,7,20]
       root=20; leftSize=1
       left ranges [2..2] and [1..1] -> leaf 15
       right ranges [4..4] and [2..2] -> leaf 7

Notice that the left call never consumes postorder[3]. That boundary is why building left first works here.

Pitfalls to avoid

• Mixing explicit-range bounds with shared-cursor consumption rules.
• Including postR in a child interval; it belongs to the current root.
• Using mid instead of mid-inL as the left subtree size.
• Scanning inorder repeatedly, which can take O(n²) on a chain.

Debugging lens

Trace both child intervals on an uneven tree. If using a backward cursor instead of the reference ranges, a three-node tree exposes a wrong left-first call. Run repeated reconstructions and check both input arrays remain unchanged.

Complexity

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

Implementation notes (Go)

• Keep the map and recursive helper local to each BuildTree invocation.
• The reference uses four inclusive indices, not a captured decrementing postIdx.
• Go subslicing shares backing storage and does not copy array elements. Explicit indices make the two traversal boundaries easier to inspect; the map prevents repeated linear searches.

Contract precision

Both traversals describe the same valid tree, with unique values. Input arrays are read-only, and each call has independent traversal state.

Reconstruction checkpoint

For inorder [2,4,6,9] and postorder [2,6,4,9], what are the root and left subtree ranges? Could an explicit-range implementation build left first? Could a shared backward cursor?

Return to Binary Tree General · Module quiz