GATE1990-3-iv

Question

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

• 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

D should be correct

---

I think Option B  should be the correct answer

Answer 1

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 , could you please give any counter-example to make option (A) wrong ..I have counter-example for option (B) & (C) but I am not getting any counter-example for option (A)

---

$O(n^{2})$ never possible

less than $O(n^{2})$ is correct but equal to $O(n^{2})$ makes option A) incorrect

---

I have tried so many examples but everytime I got EPL <= n² .. if possible please give any example where EPL > n²

---

O(n²) never possible

everyone agree for this...

But option A says, the value is ≤ n². ===> it is true.

i mean 5 ≤ 25 ====> returns true.

---

actually n is leaf node what i am assuming is it correct?

---

 Well I have a theory please verify this:

Assumption: external nodes are leaf nodes.

when I will have completely filled tree having all leaf nodes at every level. If I have n external nodes implies I will be having n-1 internal nodes. This means my height of the tree should be = log(total nodes) = log(n+n-1) = log(2n-1) hence if there are n external nodes EPL will be nlog(2n-1).

option B says >= nlog(n) one might think it is true as nlog(2n-1) > nlogn hence option B is correct but wait!!

Theory to reach above conclusion:

lets say I have a complete filled binary tree( it has all leaf nodes) and if there are total of n nodes then,

Leaf nodes = $\frac{n+1}{2}$ then non-leaf nodes becomes i.e. internal nodes = $\frac{n+1}{2} - 1$

so Height of the tree:

= log($\frac{n+1}{2}+\frac{n+1}{2} - 1)$

= log($\frac{n}{2}+\frac{n}{2}+\frac{1}{2}+\frac{1}{2}-1)=log(n)$.

Hence I can say for given n nodes where it has (n+1)/2 leaf nodes and (n+1)/2-1 internal nodes will have height equal to log(n).

C. becomes false no need of reason

D. If we consider skew tree it will have external node = 1 we can't determine how many internal nodes it has at this point, but if we consider a tree which is left skew having only 2 nodes. we know EPL becomes 1. hence I can say for n=1 my EPL = 1 which satisfies option D for some special trees.

If that some special trees option is not there there could be a problem as there is no way of Identifying how many internal node a tree can have. for external node n = 1, I can even have internal node = 1000, this tells me my first A is wrong.

You can argue me with the point then why I derive nlog(2n-1)? remember its base condition was it is fully complete binary tree having present all leaf nodes at last level. It helps me to visualize EPL at balanced tree condition. If I assume it to be a skew tree then I don't think it is possible to determine the number of internal node it can have. Option B says less than or equal to nlogn. I don't have any proof here but I tried with certain value of n and it turns out option B is valid. for B only conclusion I was able to derive is it will satisfy whenever tree is balenced as nlogn < nlog(2n-1) and again for skew trees it satisfies.

So according to me option B and D should be true.

Please validate the above theory.

---

@swapnil

How b and d should be true at a time?

if d is true means then b should be false, right?

---

The question says choose one or more than one correct alternative

---

yes brother, but i am saying..

option B says ( n log n ) is minimum

but option D says (n) is possible.

they contradicting...

but we know that, atmost (n log n)

option A says it should be not greater than (n^2), then we can say option A is right along with with option D

---

Shaik Masthan WHAT IS N?

---

@ shaik you are correct but there comes a point in nlogn and O(n) where they become equal at n = 2, this must be the point when both can give same value at this must be valid for some trees. In that theory I have specified why nlogn becomes true and why O(n) becomes true as well. Please tell me if that theory is contradicting.

---

@eyeamgj

WHAT IS N?

n means, no.of external nodes, i mean to calculate total external path length, EPL, of a binary tree with n external nodes takes O(n) only...

 

@Swapnil Naik

what i am saying is

If you want to say " something is true, then it should be always true. ", i will give  counter example where option b can be false.

---

exterenal node means leaf nodes? if then please check my tree i posted above how ut is O(n).

---

external nodes means, not leaf nodes, check the image i posted on your question.

let there are two nodes, root as A and right Child B.,

then A's left is no Node, but can be possible, that is external node.

B's left and right are external nodes are there ( those are not in the part of tree )

---

Shaik Masthan not getting which r external nodes?.

---

@eyeamgj

---

Shaik external node means a node who doesn't have children => Leaf node

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html

https://en.wikipedia.org/wiki/Tree_(data_structure)

https://stackoverflow.com/questions/265809/what-is-an-internal-node-in-a-binary-search-tree

In above Diagram only B doesn't have child so it becomes external node.

If I am wrong please give me references for further evaluation.

 

---

@Swapnil Naik

i don't know why all those links conveying lef node = external node.

then what  is the mean of external edges ?

i read it some where but i didn't remember where that resource is ?

---

I don't know about external edges. I searched but didn't get any useful information.

---

EPL can't be less than nlogn in any case for binary tree. It will be equal to nlogn if it is full binary tree,otherwise it will be always greater than nlogn. We can even have EPL> n^2 if we take skewed binary tree.

---

@srestha I think you are incorrect here. $<=n^{2}$ will always hold true.

<= means "less than OR equal to". The answer will always be less than $n^{2}$ .

 '=' won't make the option wrong. Also, in the question its not <=O($n^{2}$). Its simply $<=n^{2}$.

So, the answer should be A and D.

---

@Shaik Masthan

A tree should be always connected if it is not connected it cannot be part of the tree  so those nodes are not part of the tree itself

Answer 2

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 3

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.

Answer 4

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 max 7 nodes, n=4(leaf), sum of Iw = 8

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?

Answer 5

I think A) and D)