GATE CS 2000 Q2.16 — Trees

To determine which of the relations is always true for a complete binary tree, we can analyze small counterexamples.

Recall the definitions of the traversals:

• Preorder: Root $\rightarrow$ Left $\rightarrow$ Right
• Inorder: Left $\rightarrow$ Root $\rightarrow$ Right
• Postorder: Left $\rightarrow$ Right $\rightarrow$ Root

Counterexample 1: Complete Binary Tree with 2 nodes ($N = 2$)

    A
   /
  B

• Preorder: $A, B \implies \text{LASTPRE} = B$
• Inorder: $B, A \implies \text{LASTIN} = A$
• Postorder: $B, A \implies \text{LASTPOST} = A$

Here, $\text{LASTIN} \neq \text{LASTPRE}$ (since $A \neq B$). This disproves Option B.

Counterexample 2: Complete Binary Tree with 3 nodes ($N = 3$)

    A
   / \
  B   C

• Preorder: $A, B, C \implies \text{LASTPRE} = C$
• Inorder: $B, A, C \implies \text{LASTIN} = C$
• Postorder: $B, C, A \implies \text{LASTPOST} = A$

Here:

• $\text{LASTIN} \neq \text{LASTPOST}$ (since $C \neq A$). This disproves Option A.
• $\text{LASTPRE} \neq \text{LASTPOST}$ (since $C \neq A$). This disproves Option C.

Since none of the statements in A, B, or C are always true, the correct choice is D.