The GATE Grind

GATE 2025 CS (CS2) – Question 13

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

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?

  1. $\frac{n-2}{2}$
  2. $\frac{n-1}{2}$
  3. $\frac{n}{2}$
  4. $\frac{n+1}{2}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\frac{n-1}{2}$

Explanation

In a full binary tree, leaves = internal nodes + 1. So $n = 2i + 1$ and $i = (n-1)/2$.