CodeWithYash

Intermediate · Module 13 · Lesson 6

Tree construction

Rebuild trees from traversal orders.

15–25 min readLesson 75 of 123

Lesson 75 of 123

1d streak

Tree Reconstruction from Traversal Orders

Can a unique binary tree be reconstructed from traversal outputs? A single traversal is ambiguous. However, combining Preorder and Inorder (or Postorder and Inorder) uniquely determines the tree.

Reconstruction Logic: Preorder + Inorder
Preorder: [ 3 | 9 | 20, 15, 7 ]  -> First element 3 is ALWAYS the ROOT!
Inorder:  [ 9 | 3 | 15, 20, 7 ]  -> Find root 3 in Inorder:
            ^       ^
        Left Subtree Right Subtree
        (Values: 9)  (Values: 15, 20, 7)

Recursive Divide & Conquer:
1. Root = 3.
2. Left Subtree built from Inorder [9] and Preorder [9].
3. Right Subtree built from Inorder [15, 20, 7] and Preorder [20, 15, 7].
Runtime: O(n) using a HashMap to look up root indices in Inorder in O(1)!

Cost Model

Complexity & Trade-offs

Build with index map
O(n)
O(n)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Hierarchies, ordered sets/maps, expression trees, and recursive aggregation.
  • Path, ancestor, depth, and subtree questions.
  • Maintaining sorted dynamic data with balanced trees.

Common mistakes

  • Assuming a BST is balanced without a balancing guarantee.
  • Confusing node depth with subtree height.
  • Discarding information needed by the parent instead of returning it.

Practice prompts

  • Reproduce the worked Tree construction example without looking at the trace.
  • Change one input condition and explain whether the Tree construction invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.