GATE CS 1998 Q1.24 — Trees

We need to identify the false statements among the given options.

• Statement A: A tree with $n$ nodes has $(n - 1)$ edges.
  Status: TRUE. By definition, any connected acyclic graph (tree) with $n$ vertices contains exactly $n - 1$ edges.
• Statement B: A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
  Status: FALSE. Preorder and postorder traversals are not sufficient to uniquely reconstruct a binary tree. For example, consider the following two distinct binary trees:
  1. Tree 1: Root $A$ with left child $B$.
  2. Tree 2: Root $A$ with right child $B$.
  Both trees have the preorder traversal $[A, B]$ and postorder traversal $[B, A]$. Thus, the reconstruction is not unique.
• Statement C: A complete binary tree with $n$ internal nodes has $(n + 1)$ leaves.
  Status: FALSE. This property holds for a strict (or full) binary tree where every internal node has exactly 2 children. However, a complete binary tree can have nodes with only 1 child.
  For example, consider a complete binary tree with $4$ nodes:
  • Root $1$ has children $2$ and $3$.
  • Node $2$ has a left child $4$.
  Here, the internal nodes are $1$ and $2$ ($n = 2$), and the leaves are $3$ and $4$ (number of leaves $= 2$). Since $2 \neq n + 1$, the statement is false.
• Statement D: The maximum number of nodes in a binary tree of height $h$ is $2^{h+1} - 1$.
  Status: TRUE. Under the standard definition where the height of a single-node tree is $0$, the maximum number of nodes at level $i$ is $2^i$. Summing this from level $0$ to $h$ gives: $$\sum_{i=0}^{h} 2^i = 2^{h+1} - 1$$

Since the question asks for the false statements, the correct options are B and C.