Construct BT from Postorder and Inorder
Rebuild the tree from inorder and postorder traversals.
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder and postorder consist of unique values.
- Each value of postorder also appears in inorder.
- inorder is guaranteed to be the inorder traversal of the tree.
- postorder is guaranteed to be the postorder traversal of the tree.
Intuition
To construct bt from postorder and inorder — to rebuild a binary tree from those two traversals — you need to know what each one contributes. Neither is enough alone — many different trees share an inorder sequence — but together they pin down exactly one tree. Postorder visits left, then right, then the node. So its last element is always the root of whatever range you are looking at. That gives you a root for free. Inorder visits left, node, right. Once you know the root's value, finding it inside the inorder sequence splits that sequence into two pieces: everything before it is the left subtree, everything after is the right subtree. The split also tells you the sizes of both subtrees, which is what lets you carve up the postorder range to match. Now the recursion writes itself: take the last postorder element as the root, split inorder around it, and recurse on the two halves. The one detail that trips people up is the order of the recursive calls. If you consume postorder from the back with a single moving pointer, the element before the root is the root of the right subtree, not the left — postorder places the right subtree immediately before the node. So you must build: - Right subtree first, then left, or the shared pointer hands each call the wrong root. That is the mirror image of the preorder-plus-inorder version, where the pointer moves forward and left is built first.
To construct binary tree from postorder and inorder traversal, postorder read backwards gives roots in root-right-left order, so consuming it from the end means building the right subtree before the left. It's the preorder construction mirrored — the same code with the cursor moving the other way and the two recursive calls swapped.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(n) space.
Index the inorder values first
Build a hash map from value to index over the inorder array. Without it, each recursive call would scan to find the root and the algorithm degrades to O(n²). This one-time O(n) map is what keeps the whole build linear, and it assumes values are unique, which the problem guarantees.
Take the root from the end of postorder
Keep a pointer starting at the last index of the postorder array. The value there is the root of the current subtree. Create the node, then decrement the pointer so the next call sees the next root in line.
Split the inorder range around the root
Look up the root's index in the map. Everything to its left in the inorder range forms the left subtree, everything to its right forms the right subtree. Pass ranges as index bounds rather than slicing arrays — slicing copies data and quietly turns a linear algorithm quadratic.
Build the right subtree before the left
Recurse on the right range first, then the left. This ordering is mandatory, not stylistic: walking postorder backwards yields the node, then its right subtree's root, then its left. Building left first would hand the left subtree a root that belongs to the right.
Stop when the range is empty
If the left bound passes the right bound, there are no nodes in this range, so return null. This is the base case that terminates every branch, and it also handles the empty-tree input without a special check.
Attach and return
Assign the two recursive results to the node's right and left, then return the node. Because the pointer is shared across all calls, each subtree consumes exactly the postorder elements that belong to it — no explicit accounting of which range of postorder goes where is required.
Cost of the reconstruction
Every node is created once and every lookup is O(1) through the map, so time is O(n). Space is O(n) for the map plus O(h) for the recursion stack, which is O(log n) on a balanced tree and O(n) on a degenerate one.
Solution & live demo
Common pitfalls
Building left before right
node.left = build(lo, idx[val] - 1) node.right = build(idx[val] + 1, hi)
node.right = build(idx[val] + 1, hi) node.left = build(lo, idx[val] - 1)
Walking postorder backwards encounters the right subtree's nodes before the left's. Building left first makes the cursor hand right-subtree values to the left branch, producing a structurally valid but completely wrong tree.
Starting the cursor at 0
self.post = 0
self.post = len(postorder) - 1
The root is the last element of postorder, not the first. Starting at the front takes a leaf as the root and the whole reconstruction collapses.
Incrementing the cursor
val = postorder[self.post]; self.post += 1
val = postorder[self.post]; self.post -= 1
The array is consumed from the end towards the front, so the cursor moves backwards. Incrementing runs off the end immediately.
Edge cases
post = in = [x] → leaf.
Right recursion returns immediately at every level; pointer discipline still holds.