The total external path length, $\text{EPL},$ of a full binary tree with $n$…
GATE · 1990 · CS · Question 3 subpartsModified — slightly modified from the official paper; see the solution
The total external path length, $\text{EPL},$ of a full binary tree with $n$ external nodes is, $\text{EPL}= \displaystyle \sum_{w} I_w$, where $I_{w}$ is the path length of external node $w$),
- A.
$\leq n \log_{2} n$ always.
- B.
$\geq n \log_{2} n$ always.
- C.
Equal to $n^{2}$ always.
- D.
$O(n)$ for some special trees.
Attempted by 3 students.
Sign up free to check your answer
Sign up freeLoading lesson…