93 views

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with $n$ external nodes is, $EPL= \sum_{w} Iw$, where $I_{w}$ is the path length of external node $w$),

1. $\leq n^{2}$ always.
2. $\geq n \log_{2} n$ always.
3. Equal to $n^{2}$ always.
4. $O(n)$ for some special trees.
asked in DS | 93 views
D should be correct

External node means leaf.

a binary tree has at most n/2 Leaves. Means at most or order n.

the length of path from root to leaf is at most log(n)

summing over all such nodes gives nlog(n) Lower bound. Option B

this can be always less than order n squared in the worst case. Option A.

option C is not possible because it can be less than that.

Option D is not possible because it is always greater than order n.
–1 vote
I think A) and D)