Pattern visualizer
Construct Binary Tree from Inorder and Postorder Traversal
Postorder always ends with the root of whatever range it is currently building. So working backward through postorder, popping one root at a time, and locating each root in inorder splits the remaining indices into a left part and a right part to recurse on. Because postorder is laid out as [left subtree, right subtree, root], the elements just before any root belong to its RIGHT subtree — so every call must finish the right half before the left half, or the shrinking postIdx pointer falls out of sync. Animated on: inorder=[9,3,15,20,7], postorder=[9,15,7,20,3] — rebuild the original tree (expected [3,9,20,null,null,15,7])..
Root from the back of postorder, right subtree before left
Call stack
postorder's LAST unconsumed element (index 4) is 3 — a postorder listing always ends with the root of whatever range it is building, so build(0,4) creates the tree's root, node 3. In inorder, 3 sits at index 1, splitting [0..4] into a left part (index 0..0) and a right part (index 2..4). Recursing into the right half FIRST keeps postIdx in sync: postorder is laid out as [left..., right..., root], so the elements just before 3 belong to its right subtree.
1FUNCTION build(inStart, inEnd):2 IF inStart > inEnd: RETURN null3 rootVal <- postorder[postIdx]4 postIdx <- postIdx - 15 node <- NEW NODE(rootVal)6 mid <- INDEX_OF(rootVal, inorder)7 node.right <- build(mid + 1, inEnd)8 node.left <- build(inStart, mid - 1)9 RETURN node
← / → step · space play · Home restart