Let H,𝐼, 𝐿, and 𝑁 represent height, number of internal nodes, number of leaf nodes, and the total number…

Question

Let H,𝐼, 𝐿, and 𝑁 represent height, number of internal nodes, number of leaf nodes, and the total number of nodes respectively in a rooted binary tree.

Which of the following statements is/are always TRUE?

Accepted Answer

Correct answer: A, B, C — Key insight: relate counts of nodes with 0, 1, and 2 children. Let n0 be the number of leaves (L), n1 the number of nodes with one child, and n2 the number of nodes with two children. Every binary tree satisfies n0 = n2 + 1 (this follows from counting child pointers or by induction). The number of internal nodes is I = n1 + n2, and since n1 ≥ 0 we get L = n2 + 1 ≤ n1 + n2 + 1 = I + 1. Thus L ≤ I + 1 always holds. Equality occurs when n1 = 0, i.e., in full (proper) binary trees where every internal node has two children.

Answer

A. 𝐿 ≤ 𝐼 + 1

Answer

B. 𝐻 + 1 ≤ 𝑁 ≤ 2𝐻+1 − 1

Answer

C. 𝐻 ≤ 𝐼 ≤ 2𝐻 − 1

Answer

D. 𝐻 ≤ 𝐿 ≤ 2𝐻−1

Let H,𝐼, 𝐿, and 𝑁 represent height, number of internal nodes, number of…