DSA Tracker

Visualize

Construct Binary Tree from Inorder and Postorder Traversal

Root from the back of postorder, right subtree before left

time O(n)space O(n)

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.

Details

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]).

Problem:Construct Binary Tree from Inorder and Postorder TraversalMedium

Root from the back of postorder, right subtree before left

step 1 / 10

3
0..4

Call stack

build(0,4)

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.

Pseudocode
1FUNCTION build(inStart, inEnd):
2  IF inStart > inEnd: RETURN null
3  rootVal <- postorder[postIdx]
4  postIdx <- postIdx - 1
5  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

Every step in words

Show all 10 steps
  1. 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.
  2. postorder[3] = 20 is the next unconsumed element, so build(2,4) creates node 20. In inorder, 20 sits at index 3, splitting [2..4] into a right part (index 4..4) built first, then a left part (index 2..2).
  3. Only index 4 is left in this range, so build(4,4) creates node 7 with no room on either side — it will turn out to be a leaf.
  4. Both of node 7's index ranges came back empty, so it gets no children — it is a leaf. Its frame pops back to build(2,4).
  5. Only index 2 is left in this range, so build(2,2) creates node 15 with no room on either side — it will turn out to be a leaf.
  6. Both of node 15's index ranges came back empty, so it gets no children — it is a leaf. Its frame pops back to build(2,4).
  7. Both halves of node 20 are done (left=15, right=7), so build(2,4) returns node 20 complete. Its frame pops back to build(0,4).
  8. Only index 0 is left in this range, so build(0,0) creates node 9 with no room on either side — it will turn out to be a leaf.
  9. Both of node 9's index ranges came back empty, so it gets no children — it is a leaf. Its frame pops back to build(0,4).
  10. Every range has been built. build(0,4) returns the finished root, node 3 — reconstructing the tree with no calls left on the stack.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Construct Binary Tree from Inorder and Postorder Traversal in the editorAll Binary Trees problemsBack to roadmap