Construct Binary Tree from Inorder and Postorder Traversal
Problem
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
The last postorder element is always the current root. Find that value's position in the inorder array — left side becomes the left subtree, right side the right subtree. Recurse from the back of postorder, building the right subtree before the left.
inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]level-order: [3, 9, 20, _, _, 15, 7]def build_tree(inorder, postorder):
pos = {v: i for i, v in enumerate(inorder)}
pi = [len(postorder) - 1]
def rec(lo, hi):
if lo > hi: return None
v = postorder[pi[0]]; pi[0] -= 1
node = TreeNode(v)
m = pos[v]
node.right = rec(m + 1, hi)
node.left = rec(lo, m - 1)
return node
return rec(0, len(inorder) - 1)function buildTree(inorder, postorder) {
const pos = new Map();
inorder.forEach((v, i) => pos.set(v, i));
let pi = postorder.length - 1;
function rec(lo, hi) {
if (lo > hi) return null;
const v = postorder[pi--];
const node = { val: v, left: null, right: null };
const m = pos.get(v);
node.right = rec(m + 1, hi);
node.left = rec(lo, m - 1);
return node;
}
return rec(0, inorder.length - 1);
}class Solution {
int pi;
Map<Integer,Integer> pos = new HashMap<>();
int[] post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
post = postorder; pi = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return rec(0, inorder.length - 1);
}
TreeNode rec(int lo, int hi) {
if (lo > hi) return null;
int v = post[pi--];
TreeNode node = new TreeNode(v);
int m = pos.get(v);
node.right = rec(m + 1, hi);
node.left = rec(lo, m - 1);
return node;
}
}int pi;
unordered_map<int,int> pos;
vector<int> post_;
TreeNode* rec(int lo, int hi) {
if (lo > hi) return nullptr;
int v = post_[pi--];
auto node = new TreeNode(v);
int m = pos[v];
node->right = rec(m + 1, hi);
node->left = rec(lo, m - 1);
return node;
}Explanation
We rebuild a binary tree from its inorder and postorder lists. The key fact is that the last value in postorder is always the root of the current subtree, and inorder then tells us how to split everything else into left and right halves.
We pre-build a lookup map pos from value to its index in inorder, so we can find any root's split point instantly. A pointer pi walks postorder from the back, handing us roots one at a time.
In postorder the layout is left, right, root, so reading from the end we see root, then the right subtree, then the left. That is why the recursion builds node.right before node.left. The range [lo, hi] tracks which slice of inorder this subtree covers; lo > hi means empty.
Example: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]. Last value 3 is the root; in inorder it sits at index 1, so left is [9] and right is [15, 20, 7]. Next from the back, 20 roots the right subtree, splitting into 15 and 7.
With the map giving O(1) splits and each value used once, the tree is rebuilt in linear time.