139 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 | 139 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.
Here the question asked for binary tree

It can be of 2 types (1) skewed tree (2) Balanced binary tree or AVL tree

We have to find external path length i.e. leaf node

We also know cost of external path = leaf node value * lenth of path

Now for balanced tree external path length=$n\times log n$

But for skewed tree it will be $O\left ( n \right )$ only

So, ans will be D)
–1 vote
I think A) and D)