6,037 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

Best answer
22 votes
22 votes

Here, $n$ denotes the number of external (leaf) nodes and not the total number of nodes.

  1. By adding an edge to the root of a skewed binary tree of say $10$ nodes, we get a binary tree of $11$ nodes having $2$ external nodes of path lengths $9$ and $1$ respectively giving $\text{EPL} = 9+1 = 10 > 2^2.$ So, option A is false.
  2. This is always TRUE. The minimum $\text{EPL}$ for a given number of external nodes $n$ happens for a full binary tree. In this case when we have $n$ external nodes and $(2n-1)$ total nodes and each external node will have a path length of $\log_2 (2n-1)$ giving total external path length, $\text{EPL} = n \log_2 (2n-1).$ Now, if we try to add any amount of skeweness to this full binary tree we can see that $\text{EPL} > n \log_2 (2n-1).$
  3. False as shown for option A.
  4. False as shown for option B.

Correct option: B.

edited by
7 votes
7 votes
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)
4 votes
4 votes
option A isn't right . Here's a counter example , imagine a skewed tree with 2 leaf nodes right at the end of the chain eg;

Node1 - Node2 - Node3 - Node4 - Node5 -  leaf 1

                                                                         |- leaf2

 

here EPL is 10 with 2 external nodes or leaf nodes and it's greater than 4
1 votes
1 votes

Main point: n is the number of external nodes

Option A:

       Cant be the answer. Take an example binary tree with height 2, it will have min 3 nodes(left skew), n=1(leaf), sum of Iw = 2

Option C:

       From above example, not true.

Option D: 

       If a tree has 2 nodes, n = 1 and Iw = 1. It holds true

Option B:

       This always works….then why is it not the answer?

(B,D)

edited 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,492 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...