GATE 2025 CS2 Q.13: solution and answer

GATE 2025 · CS2Q.13 · 1 mark · MCQ

Consider a binary tree $T$ in which every node has either zero or two children. Let $n > 0$ be the number of nodes in $T$ .

Which ONE of the following is the number of nodes in $T$ that have exactly two children?

(A)
$\frac{n - 2}{2}$
(B)
$\frac{n - 1}{2}$
(C)
$\frac{n}{2}$
(D)
$\frac{n + 1}{2}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of nodes with exactly two children is (n-1)/2 — option (B).

Official answer: BSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

Let n0 = number of leaf nodes (0 children) and n2 = number of nodes with exactly 2 children. Since every node has either 0 or 2 children, n1 = 0, so total nodes n = n0 + n2.
Count total edges two ways. Every node except the root has exactly one incoming edge from its parent, so total edges = n - 1.
Also, each node with exactly two children contributes exactly 2 outgoing edges (and nodes with 0 children contribute 0), so total edges = 2 * n2.
Equating the two counts: n - 1 = 2 * n2, so $n_{2} = \frac{n - 1}{2}$ .
This matches option (B), and is the standard identity n0 = n2 + 1 for such trees (since n = n0 + n2 = (n2+1) + n2 = 2n2 + 1 gives the same result).

KEY IDEA

In a binary tree where every node has 0 or 2 children (a "full" or "proper" binary tree), counting edges two ways (n-1 total edges vs. 2 edges per 2-child node) gives n2 = (n-1)/2, equivalently the identity n0 = n2 + 1.

WATCH OUT FOR

Confusing "full binary tree" (every node has 0 or 2 children — the condition given here) with "complete binary tree" (all levels filled except possibly the last), or misremembering the identity as n0 = n2 (rather than n0 = n2 + 1), which would incorrectly give n2 = n/2, option (C).

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2025 CS2 Q.13: solution and answer

Answer and solution

More Trees & heaps questions