6,038 views
21 votes
21 votes

The total external path length, $\text{EPL},$ of a 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$),

  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.

5 Answers

0 votes
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.
reshown by
Answer:

Related questions

29 votes
29 votes
6 answers
2
makhdoom ghaya asked Nov 22, 2016
9,204 views
Indicate which of the following well-formed formulae are valid:$\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)...
20 votes
20 votes
3 answers
3
makhdoom ghaya asked Nov 22, 2016
9,024 views
Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:$R_{1} \cap R_{2}$ is not regular.$R_{1} \cup R_{2}$ is regular.$\Sigma^{*}-R_{1}$ is regu...
46 votes
46 votes
2 answers
4
makhdoom ghaya asked Nov 22, 2016
12,494 views
It is undecidable whether:An arbitrary Turing machine halts after $100$ steps.A Turing machine prints a specific letter.A Turing machine computes the products of two numb...