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
GATE 1995 · Programming and Data Structures · Binary Tree · medium
Answer: The number of nodes of degree 2 in a binary tree with n leaves is n - 1. Answer: B.
Set up node count equation: Let N = total nodes, n_0 = leaves (= n), n_1 = degree-1 nodes, n_2 = degree-2 nodes. So N = n + n_1 + n_2.
Set up edge count equation: A tree with N nodes has N-1 edges. Each edge comes from a child relationship: degree-1 nodes contribute 1 edge each, degree-2 nodes contribute 2 edges each, leaves contribute 0. So: N - 1 = n_1 + 2*n_2.
Solve for n_2: From step 1: N = n + n_1 + n_2, so N - 1 = n + n_1 + n_2 - 1. From step 2: N - 1 = n_1 + 2*n_2. Equating: n + n_1 + n_2 - 1 = n_1 + 2*n_2. Simplifying: n - 1 = n_2. So the number of degree-2 nodes = n - 1.