GATE CS 2025 Set 2 Q.13: Binary Trees, Binary Search Trees and Balanced Trees

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?

$\frac{n - 2}{2}$

$\frac{n - 1}{2}$

$\frac{n}{2}$

$\frac{n + 1}{2}$

Official answer and solution

Official answer: B
From: Official GATE 2025 answer key

Solution

Use the relationship $n = 2i + 1$ between the total nodes $n$ and the internal nodes $i$ in a full binary tree.

Let $i$ be the number of internal nodes (nodes with exactly two children) and $L$ be the number of leaf nodes (nodes with zero children). In any full binary tree, $L = i + 1$ . Since the total number of nodes is $n = i + L$ , we have:

n = i + (i + 1) = 2i + 1 \implies i = \frac{n - 1}{2}

Final answer

Option (B)

Common trap

Confusing the number of leaf nodes $(n+1)/2$ with the number of internal nodes $(n-1)/2$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 13 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source