GATE CS 1990 Q3-iv — Trees

The total external path length ($\text{EPL}$) of a binary tree with $n$ external nodes is the sum of the depths of all $n$ external nodes. Let $d_i$ denote the depth of the $i$-th external node for $1 \le i \le n$. Thus, $\text{EPL} = \sum_{i=1}^{n} d_i$.

By Kraft's Inequality for any binary tree, the depths of the external nodes must satisfy:

Using the properties of entropy or Gibbs' inequality, we can find the minimum value of $\sum d_i$. Let $p_i = \frac{1}{n}$ for all $i$. Then:

This lower bound is achieved when the binary tree is perfectly balanced, where each external node has a depth of approximately $\log_2 n$. Therefore, $\text{EPL} \ge n \log_2 n$ always holds.