GATE CSE 1990 | Question: 3-iv

Question

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$),

• A. $\leq n^{2}$ always.
• B. $\geq n \log_{2} n$ always.
• C. Equal to $n^{2}$ always.
• D. $O(n)$ for some special trees.

Comments

since here we are talking about general binary tree which can have 0,1,2 children then option A will become false .

REASON : let us take a quick example , let us have a left skewed binary tree having 10 nodes and we are adding a new node say at the second last node the 9th node then we are having 2 external node and total of 11 nodes then accoding to which the sum of path lengths will become 9+9=18, which is greater then 2^2 i.e 4 hence it is false.

option A can be true only if explicitly it was given in the question that the binary tree is a full binary tree then the bounds will be nlogn<=EPL<=n^2

 

---

https://www.youtube.com/watch?v=9fdvoQ6KZjE
This may help anyone who wants video solution.

---

For better understanding:

External Path Length -- from Wolfram MathWorld

Answer 1

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

• A. 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.
• B. 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).$
• C. False as shown for option A.
• D. False as shown for option B.

Correct option: B.

Comments

@Arjun sir, why option D is false? If we have a perfect binary tree of 3 nodes then the total external path length would be 2 and the external nodes would also be true. In this case the EPL would be O(n)

---

See the example given below:

Here EPL= (n-1)*1 + 1*2 = n-1, which is clearly < nlogn . Option B says EPL>= nlogn always. Therefore option B should be false.

---

@ashutoshxX Your example is not a Binary Tree. The question is asking about binary tree.

Answer 2

 

Therefore, Option B) is correct.

Answer 3

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)

Comments

@ srestha

equal to O($n^{2}$) makes option A incorrect

but this is possible though. Let’s take a example.. see below figure ignore captions..

here external node is B only and EPL(external path length is 1).

so clearly satisfying $1\leqslant ^{}1^{2}$

so it is satisfying equal to O($n^{2}$) also.

 

---

how can for skewed tree is O(n)  ? //O(1)

for skewed tree,let say number of external nodes = n = 1.

 how can external path length for skewed tree is O(1)//O(n)=O(1).

so,option d is wrong

the external path length for skewed tree should be O(N -1) or O(depth of tree)//N is the total no of nodes

---

@ankitgupta.1729 as option A mentions "always" so we need only one counter to make it false right?

Answer 4

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

Answer 5

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)

Comments

EPL is indeed less than $n^2$. How A is wrong here? $ 8 < 4*4 $

---

@neel19 now A is wrong

---

I never said A isn’t wrong. Just your example was wrong previously. :)

Answer 6

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.

Comments

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

Not true in the case of a skewed binary tree.