The GATE Grind

GATE 2024 DA – Question 52

Programming, Data Structures and Algorithms · Stacks, queues, linked lists, trees and hash tables · 2 marks · Multiple select

Let $H$, $I$, $L$, and $N$ 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?

  1. $L \le I + 1$
  2. $H + 1 \le N \le 2^{H+1} - 1$
  3. $H \le I \le 2^H - 1$
  4. $H \le L \le 2^{H-1}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $L \le I + 1$; (B) $H + 1 \le N \le 2^{H+1} - 1$; (C) $H \le I \le 2^H - 1$

Explanation

A: each internal node has at most 2 children, so the number of leaves is at most $I + 1$ (equality for a full binary tree). B: a tree of height $H$ has at least $H + 1$ nodes (a path) and at most $2^{H+1} - 1$ nodes (a complete tree). C: a path of height $H$ has $H$ internal nodes, the least possible, and a complete tree has $2^H - 1$, the most possible, so the bounds always hold. D: a path of height $H$ has only one leaf, which is less than $H$ when $H \ge 2$, so D fails.