Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _____.

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 199

Trees

In any binary tree $T$ , let:

$n_0$ = number of leaf nodes (nodes with degree 0 / no children)
$n_1$ = number of nodes with exactly 1 child
$n_2$ = number of nodes with exactly 2 children

The total number of nodes is $n = n_0 + n_1 + n_2$ .

The total number of edges in any tree with $n$ nodes is $E = n - 1$ .

Counting edges by outgoing degree of nodes:

E = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 = n_1 + 2n_2

Equating the two expressions for $E$ :

n_0 + n_1 + n_2 - 1 = n_1 + 2n_2 \implies n_2 = n_0 - 1

Given $n_0 = 200$ :

n_2 = 200 - 1 = 199

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Trees previous year question is Q25 of the GATE CSE 2015 Set 3 paper. Find more GATE CSE PYQs on Trees in Programming and Data Structures, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Trees PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Trees in GATE CSE

Trees has 13 GATE CSE PYQs across 11 papers from 2012 to 2026. 5 of them are 1-mark NAT questions like this one, and it is the only one in GATE CSE 2015 Set 3.

How GATE tests Trees

More from GATE CSE 2015 Set 3

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.