Construct Binary Tree from Inorder and Postorder Traversal
Understanding the Problem
We are given the inorder and postorder traversals of a binary tree and have to rebuild the tree.
Each traversal contributes a different piece of structural information. Postorder visits left subtree, right subtree, root, so the last element of the postorder array is the root of the whole tree. Inorder visits left subtree, root, right subtree, so once we locate that root value in the inorder array, everything before it belongs to the left subtree and everything after it belongs to the right subtree.
This splits the problem into two smaller copies of itself: rebuild the left subtree from its portion of both arrays, rebuild the right subtree from its portion, and attach both to the root. Splitting the inorder array is direct because the root's position marks the boundary. Splitting the postorder array requires knowing how many nodes the left subtree contains, and the inorder split provides that count.
Key Constraints:
1 <= inorder.length <= 3000→ n is small enough that an O(n^2) solution passes, but O(n) is reachable with a single hash map.-3000 <= inorder[i], postorder[i] <= 3000→ Values fit in a 32-bit integer, and any number outside this range (such as 3001) can act as a sentinel that never matches a node value.- All values are unique → Each value has one unambiguous position in the inorder array, so every split is well defined. With duplicates, the two traversals would not determine a unique tree.
Approach 1: Recursion with Linear Search
Intuition
The recursion follows directly from how the two traversals encode structure. The last element of any postorder segment is that subtree's root. Finding the root's position in the corresponding inorder segment splits the segment into left and right subtrees. Repeat the same step on each half until the segments are empty.
Splitting the postorder segment takes one extra calculation. If the root sits at index rootIndex in the inorder array and the current inorder range starts at inStart, the left subtree contains leftSize = rootIndex - inStart nodes. Postorder lists the entire left subtree before the right subtree, so those nodes occupy the first leftSize positions of the postorder segment: [postStart, postStart + leftSize - 1] holds the left subtree, [postStart + leftSize, postEnd - 1] holds the right subtree, and the root itself sits at postEnd.
Algorithm
- If the current range is empty (start > end), return null.
- Take the last element of the current postorder range as the root.
- Search for this root value in the inorder array (linear scan).
- Calculate the size of the left subtree from the root's position in inorder.
- Recursively build the left subtree using the left portions of both arrays.
- Recursively build the right subtree using the right portions of both arrays.
- Return the root node.
Example Walkthrough
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3].
Code
- Time Complexity: O(n^2). We make n recursive calls (one per node), and at each call we do a linear search through the inorder array to find the root, which takes O(n) in the worst case. So total work is O(n^2).
- Space Complexity: O(h) for the recursion stack, where h is the height of the tree (O(n) worst case for a skewed tree). This excludes the O(n) output tree.
The recursion itself touches each node once; only the repeated linear searches push the cost to O(n^2). The position of every value in the inorder array never changes between calls, so those searches recompute the same information. The next approach computes all positions once, up front.
Approach 2: Recursion with Hash Map
Intuition
Since all values are unique, a hash map from value to inorder index, built once before the recursion starts, turns every root lookup from O(n) into O(1). That makes the entire algorithm O(n).
The recursive logic stays the same: the last element of the current postorder segment is the root, its position in inorder determines the left subtree size, and both arrays are split accordingly. The only change is that the lookup is now a hash map query instead of a loop.
Algorithm
- Build a hash map mapping each value in the inorder array to its index.
- Call the recursive build function with the full ranges of both arrays.
- At each recursive call, if the range is empty, return null.
- Take the last element of the current postorder range as the root.
- Look up the root's index in the inorder array using the hash map (O(1)).
- Calculate the left subtree size as
rootIndex - inStart. - Recursively build the left subtree and right subtree with the appropriate ranges.
- Return the root node.
Example Walkthrough
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3].
Code
- Time Complexity: O(n). Building the hash map takes O(n). Each of the n nodes is processed exactly once in the recursion, and the root lookup is O(1) per call. Total: O(n).
- Space Complexity: O(n). The hash map stores n entries. The recursion stack adds O(h), where h is the height of the tree (O(n) worst case for a skewed tree).
O(n) time cannot be improved, since every node has to be created. The hash map, though, costs O(n) extra space on top of the recursion stack. A different recursion order removes it.
Approach 3: Two Pointers Without a Hash Map
Intuition
Reading the postorder array from the end produces: root, then the right subtree, then the left subtree (each subtree appearing in this same reversed order). A recursion that always builds the right child before the left child can therefore consume postorder back to front with a single moving index, one element per node, with no range arithmetic and no hash map.
What remains is detecting where each subtree ends. A second index walks the inorder array from the end. Reversed inorder is: right subtree, root, left subtree. While a node's right subtree is being built, the elements consumed from reversed inorder are exactly that right subtree, so the moment the inorder pointer reaches the node's own value, the right subtree is finished. Each recursive call therefore carries a stop value: create nodes until the current inorder element equals stop, then return null. The right child's call uses the parent's value as its stop. The left child's call reuses the stop inherited from the parent, because in reversed inorder the left subtree runs up to the same boundary that delimited the parent's whole subtree.
The initial call needs a stop value that matches nothing. Values are bounded by 3000, so 3001 works as a sentinel.
Algorithm
- Initialize
postIndexandinIndexto the last positions of their arrays. - Call the recursive build function with the sentinel stop value 3001.
- If
postIndexis below 0, or the current inorder element equals the stop value, return null. - Create a node from
postorder[postIndex]and decrementpostIndex. - Build the right subtree with the new node's value as the stop value.
- Decrement
inIndex. This consumes the node's own value in the inorder array. - Build the left subtree with the inherited stop value.
- Return the node.
Example Walkthrough
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]. Both pointers start at index 4.
Code
- Time Complexity: O(n). Each node is created once, each pointer moves exactly n positions in total, and every recursive call does constant work.
- Space Complexity: O(h) for the recursion stack, where h is the height of the tree (O(n) worst case for a skewed tree). No hash map or other auxiliary structure is needed.