DSA problem
Construct Binary Tree from Inorder and Postorder Traversal
Given two arrays inorder and postorder representing the inorder and postorder traversals of a binary tree with distinct values, reconstruct and return the tree. The pair of traversals uniquely identifies the tree.
The structural insight mirrors the preorder/inorder construction, but with a twist: in postorder, the root of every subtree is the last element, not the first. So we walk postorder from the back, consuming the next root via a shared index that decreases. The position of that root inside inorder splits the inorder array into the left subtree (everything before the split) and the right subtree (everything after).
The twist forces us to build the right subtree before the left. Why? Because if we consume the postorder array from the end, the element immediately preceding the current root is the root of the right subtree (which is the last subtree built in postorder). If we recursed left first, we'd grab the wrong index.
The implementation uses a hashmap value → index for inorder (O(n) preprocessing) and a shared postIdx initialized to n - 1. The recursion build(inLo, inHi) returns null when the range is empty, otherwise consumes postorder[postIdx--] as the root, splits at idx[rootVal], builds the right subtree, then the left. Total work is O(n) time and O(n) space.
Examples
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3][3,9,20,null,null,15,7]inorder = [-1], postorder = [-1][-1]inorder = [1,2,3,4], postorder = [1,3,2,4][4,2,null,1,3]Constraints
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder and postorder consist of unique values.
- Every value in postorder also appears in inorder.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.