GATE CSE 1995 | Question: 1.17

Question

A binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is

• A. $\log_2 n$
• B. $n-1$
• C. $n$
• D. $2^n$

Comments

Key Point: Don't memorize these relations between Internal nodes and leaf nodes. It varies as per definition of degree. So go by definition in question ONLY.

Like if "Degree is # of children of a node" than its n₂=n₀-1 ( where n₂ is # Internal nodes having degree 2 & n₀ is # leaves with degree 0)

And if "Degree is # of neighbors of a node" than its n₃=n₁-2 ( where n₃ is # Internal nodes having degree 3 & n₁ is # leaves with degree 1)

Answer 1

The highly rated answer for this question on GO is excellent still I would like to tell intuition behind the concept

Let n be total number of leaf nodes, intuition is for every 2 leaf nodes there must be a node where separation occurs (that is degree of node 2) to generate two leaf nodes otherwise if no such node exists then there are two trees, so now consider all the node where separation occurred, as leaf node all at same time now for them also separation must occur this will go on till we reach to the 1 i.e n/2 internal, then after considering n/2 as internal their n/4 internal and so on till we reach 1, so n/2+n/4+n/8+...+n/2^log n =n*(1-(1/2)^log(n)-1)/1-0.5= n-1 internal node

Answer 2

Solve by taking examples

if we have only 3 nodes, q internal node 2 leaf node

7 nodes --→ 4 leaves and 3 internal

15 nodes---→ 8 leaves and 7 internal

$2^n-1$ nodes ---→ $2^{n-1}+1$ leaves and $2^{n-1}$ internal nodes

clearly only a gap of 1 is there

Hence answer is n-1