Construct Binary Tree from Inorder and Postorder Traversal

Medium#106build a tree

You get two traversals of the same binary tree with distinct values: inorder (left subtree, node, right subtree) and postorder (left subtree, right subtree, node). Rebuild the tree. Our traversals: inorder [9, 8, 4, 7, 2, 5], postorder [8, 9, 7, 5, 2, 4] — the tree, level by level, is [4, 9, 2, none, 8, 7, 5].

106 Construct Binary Tree from Inorder and Postorder TraversalWalkthrough · 1×

Example: rebuild a binary tree from its inorder [9, 8, 4, 7, 2, 5] and postorder [8, 9, 7, 5, 2, 4].

081927354254091824374255postorderinorder
not used yetinorder range of the current callval: the current nodewaiting for a subtreeused, subtree built

pos = {9: 0, 8: 1, 4: 2, 7: 3, 2: 4, 5: 5}: where each value sits in inorder, found in O(1)

01/56
restart · back · play · step
Speed
1function buildTree(inorder, postorder):
2 pos = map from each value to its index in inorder
3 next = len(postorder) - 1 // roots from the end
4 return build(0, len(inorder) - 1)
5
6function build(lo, hi):
7 if lo > hi:
8 return none
9 val = postorder[next]
10 next = next - 1
11 mid = pos[val]
12 node = new node(val)
13 node.right = build(mid + 1, hi) // right first
14 node.left = build(lo, mid - 1)
15 return node
state
next
–
lo
–
hi
–
val
–
mid
–
click a step to go back

← → step · space play/pause

Why it works

  1. Postorder ends with the root, and in inorder the root stands between its left and right subtrees: one look-up in pos splits the range into the two subtrees.
  2. Read from the end, postorder is node, right subtree, left subtree. So the right side is built first: then next, moving only backwards, always points at the root of the range being built.
  3. Each half is the same problem on a smaller range, so the same function builds it; an empty range is an empty subtree.

Complexity

Time O(n): every value becomes a node once, and pos finds its place in O(1). Memory O(n): pos holds every value, and the call stack is as deep as the tree is tall.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.