GATE CS 2015 Set 3 Q.35 (CS Q.25): Binary Trees, Binary Search Trees and Balanced Trees

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

Your answer

Official answer and solution

Solution

Apply the fundamental binary tree relation between the number of leaves and the number of degree-2 nodes.

In any binary tree $T$ :

Every node except the root has exactly one incoming edge, so the total number of edges is:

e = n - 1 = n_0 + n_1 + n_2 - 1

Alternatively, counting edges by the outgoing degree of each parent node:

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

n_0 - 1 = n_2 \implies n_2 = n_0 - 1

Given $n_0 = 200$ leaf nodes:

n_2 = 200 - 1 = 199

Thus, the number of nodes in $T$ that have exactly two children is 199.

Final answer

199

Common trap

Assuming the tree must be strictly full or complete, whereas the identity n2 = n0 - 1 holds universally for every binary tree.

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

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