First time here? Checkout the FAQ!
+4 votes

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 by Veteran (38.7k points)   | 93 views
D should be correct

2 Answers

0 votes
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.
answered by (279 points)  
–1 vote
I think A) and D)
answered by Junior (803 points)  

Top Users Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points

25,978 questions
33,554 answers
31,011 users