Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Which structure produces level order? from Lesson 4.3.2
• 0-based array: children of index i? from Lesson 4.2.3
• What is the 4th Catalan number, and what did it count in the stack lesson? from Lesson 3.2.3

1 · The Hook

🎣

A detective has two witness statements about the same family tree: one lists people from the eldest down each branch (preorder), the other lists them left to right across the family (inorder). Neither alone identifies the family, but together they do — and the trick is to find the root in one list and split the other list around it.

2 · Predict First

🤔

Preorder A B D E C F and inorder D B E A F C. Which node is the root, and which nodes are in its left subtree? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Root A (first in preorder). In inorder, everything left of A — D, B, E — is in the left subtree; F, C are in the right subtree.

Preorder + inorder

• The first preorder element is the root.
• Find it in the inorder sequence: elements to its left form the left subtree, to its right the right subtree.
• The next |left| preorder elements are the left subtree’s preorder; the rest is the right subtree’s.
• Recurse.

For A B D E C F / D B E A F C the tree has postorder D E B F C A.

Postorder + inorder

Same idea, but the root is the last postorder element, and the left subtree’s postorder is the first |left| elements.

Which pairs are enough?

Without inorder you cannot tell whether a single child is a left or a right child. Example: the root 1 with one child 2 has preorder 1 2 and postorder 2 1 whether 2 is on the left or the right.

How many binary trees with n nodes?

The number of differently shaped binary trees with n nodes is the Catalan number C(n) (choose the size of the left subtree, multiply the counts, add up): 1, 1, 2, 5, 14, 42 for n = 0 … 5 (checked by generating all shapes). With n distinct labels placed freely, multiply by n!: n!·C(n) labelled trees. With a fixed preorder (or inorder) sequence, exactly C(n) trees remain.

4 · Visual

Rebuilt from preorder A B D E C F and inorder D B E A F C.

Preorder 1 2, postorder 2 1 …

… the same for this tree: pre + post is ambiguous.

pre:  A | B D E | C F            in:  D B E | A | F C
          root  left   right             left  root right

left subtree:   pre B D E,  in D B E   -> root B, left D, right E
right subtree:  pre C F,    in F C     -> root C, left F

            A
          /   \
         B     C
        / \   /
       D   E F

Split, then recurse on each side.

5 · Worked Examples

Example 1 Easy

Rebuild the tree with preorder A B D E C F and inorder D B E A F C; give its postorder.

Solution

See the Visual section. Postorder: D E B F C A.

Example 2 Medium

Postorder 9 1 2 12 7 5 3 11 4 8 and inorder 9 5 1 7 2 12 8 4 3 11. Give the preorder.

Solution

Root 8 (last in post). Inorder splits 9 5 1 7 2 12 | 8 | 4 3 11. Recursing on both sides gives preorder 8 5 9 7 1 12 2 4 11 3.

Example 3 GATE

How many structurally different binary trees have 5 nodes? How many binary trees with labels 1–3 are there?

Solution

C(5) = 42. Labelled with 3 distinct labels: 3!·C(3) = 6 × 5 = 30.

6 · GATE Traps

⚠️

• Preorder + postorder does not determine a binary tree unless it is strict.
• Root = first of preorder, last of postorder.
• The split sizes come from inorder; reuse them to cut the other sequence.
• Shapes: C(n); labelled trees: n!·C(n).
• A single traversal never determines the tree.

8 · Memory Hook

🧠

“Pre/post finds the root; in splits the family.”

9 · Connect the Dots

Lessons 4.3.1–4.3.3 read and rebuilt trees through their traversals. Most tree algorithms are short recursive functions that ask the same question of the left and right subtrees and combine the answers. Next lesson answers: how are counting, measuring and transforming trees written recursively, and how do trees represent arithmetic expressions?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ2 marksRebuild

Preorder 1 2 4 5 3 and inorder 4 2 5 1 3. What is the postorder?

• (A) 4 5 2 3 1
• (B) 4 2 5 3 1
• (C) 4 5 3 2 1
• (D) 5 4 2 3 1

Q2NAT1 markCatalan

How many structurally different binary trees have 4 nodes?

Numerical answer: ________

Q3MCQ1 markUniqueness

Which pair does NOT always determine a unique binary tree?

• (A) postorder + inorder
• (B) preorder + postorder
• (C) preorder + inorder
• (D) level order + inorder

Q4NAT2 marksLabelled

How many binary trees can be formed with 4 distinct labelled nodes?

Numerical answer: ________

Q5MSQ2 marksRebuild

Postorder D E B F C A and inorder D B E A F C describe a tree. Which are true?

• (A) The tree has height 2.
• (B) F is the right child of C.
• (C) B is the left child of A.
• (D) A is the root.

11 · Rule Card

• Pre + in or post + in or level + in → unique tree; pre + post only for strict trees.
• Root: first of pre, last of post; inorder splits left/right.
• Shapes with n nodes: Catalan C(n) = (2n choose n)/(n + 1).
• Labelled binary trees: n!·C(n); trees with a fixed preorder: C(n).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

tree from preorder + inordertree from postorder + inorderambiguity of preorder + postordernumber of binary trees (Catalan)labelled trees n!·C(n)

13 · Answer Vault