← 🌳 Trees & Binary Search Trees
Subtopic 3 of 5

2.3Rebuilding a tree from traversals

The idea

Reconstructing a tree: preorder gives the root, inorder splits left from right. Repeat on each side.

Think of it like this: Solving a puzzle where one clue names the boss and the other tells you who sits on each side.

Why it exists

A common 2-mark question: find the postorder (or height) from preorder and inorder.

How it works

  1. First item of preorder (last of postorder) is the root.
  2. Find it in the inorder list.
  3. Items to its left form the left subtree, items to its right the right subtree.
  4. Recurse with the matching slices of the preorder list.

Worked example: pre: 1 2 4 5 3 6, in: 4 2 5 1 6 3

Root 1. Left inorder: 4 2 5, right: 6 3. Left subtree root 2 with children 4 and 5; right subtree root 3 with left child 6. Postorder: 4 5 2 6 3 1.

Now play with it

  • →Edit the two lists and watch the tree rebuild.
  • →Try a preorder that does not match the inorder to see the error message.
425163
Postorder4 5 2 6 3 1
Height (nodes)3
Leaves3

Rule: the first preorder item is the root; find it in the inorder list, everything to its left is the left subtree, everything to its right is the right subtree. Repeat.

Check yourself

Which pair of traversals does NOT always determine a binary tree uniquely?

Remember: Preorder or postorder gives the root; inorder splits sides.
Exam notes (the dense version)

Preorder (or postorder) plus inorder determines the tree uniquely: the root comes from the preorder (first) or postorder (last) list; the inorder list splits into left and right parts. Preorder plus postorder does not determine a tree unless every node has 0 or 2 children. A BST is determined by its preorder alone (inorder is just the sorted keys).

Previous year questions: Trees & Binary Search Trees (15)

PYQs are grouped by topic, so this is the full set for Trees & Binary Search Trees; try the ones that match this subtopic. Open all 15 on the topic page.