GATE CSE 2019 | Question: 46

Question

Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. The expected value of the distance between $a$ and $b$ in $T$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal places) _________.

Comments

@riteish what is this formulae for can you give any source how it came or the proof of intuition.

---

https://gateoverflow.in/302826/gate-cse-2019-question-22

Above link 1mark question and this 2mark question from 2019 paper told us a lot about the word "independently"

people who doesn't assumed duplicate values just end up with wrong answers.

Independely took = the first and second events are independent = so same numbers can be taken twice.

---

source i derived it with the help of gpt , also i have tried for other examples.. you can trust this

Answer 1

Two leaves a and b of T are chosen uniformly and independently at random.

See the word "independently" here. It means that choice of $a$ must not affect choice of $b$ and vice versa. This implies that both $a$ and $b$ can even be the same node.

Now, we are given that the binary tree has $8$ leaves. $\left(2^3 = 8\right) \implies$ we have $3$ levels in the tree starting from $0.$ The distance in terms of number of edges between any two leaf nodes will always be even. If we consider any two leaves (not necessarily distinct)

• No. of pairs with path length $0 = 8.$ (When $a = b)$
• No. of pairs with path length $2 = 8.$ (For each of the $8$ leaf nodes, we have a pair and since the selection is independent order of the pair is also significant)
• No. of pairs with path length $4 = 16.$ (For each leaf node we have to go two levels up and while coming down we have $2$ choices. So, we get $8 \times 2 = 16$ pairs)
• No. of pairs with path length $6 = 32.$ (For each leaf node we have to go till the root, and from there while coming down it has $2 \times 2 = 4$ choices. Thus we get $8 \times 4 = 32 $ pairs.

Total number of possible pairs $ = 8 \times 8 = 64$

So, expected path length

$\quad =0 \times \frac{8}{64}  + 2 \times \frac{8}{64}+4 \times \frac{16}{64}+6 \times \frac{32}{64}= \frac{272}{64}=4.25$

Comments

see this

 

---

@Rohit139 Bhaiya, How to solve this question if they say there are 2^8 leaves or some big number ?

---

May be they won't ask for big number as they can trick for smaller one,

Answer 2

A full binary tree of $8$ leaves

Let's say we take node $H.$ The distances from $H$ to all other nodes (including itself) would be:

$\begin{array}{|c|c|c|c|c|c|c|c|}\hline
H&I&J&K&L&M&N&O\\\hline
0&2&4&4&6&6&6&6\\\hline
\end{array}$

If another node is taken, a similar table (to the one above) is attained. Therefore, all nodes have the same distances when added together. 

So, if a node is considered, the probability of choosing another node would be $1/8$ (including itself - independent choosing]. 

Therefore, $E = \frac{1}{8} \left[0+2+4+4+6+6+6+6\right] = 4.25$

Comments

@Kriti. 1212 Actually we need to multiply 1/8 only for first leaf because we are just choosing the first leaf randomly. The other leaf is not “random”. We actually pick all of the other leaves one by one and add their distances from our first leaf.

Simpler way:-

Expectation :-

 

Now here the $p_i = 1/8$ which is getting multiplied every time. Thus we can take $1/8$ as common.

Easy Way:

[Img credit: @arjuno.]

Total Path distances from $1$ leaf [say $H$] to all other leaves (incld. itself) = $2 + 4*2 + 6*4 = 2+8+24 = 34$

Since there are $8$ leaves, hence probability of picking anyone = $1/8$

Thus E(x) = $1/8 * 34 = 4.25$

---

Just another way:
let variable x denotes path length

x	P(x)
2	(8*1)/64
4	(8*2)/64
6	(8*4)/64

How i have written P(x)?
first chose a node i.e. 8 ways now,
for path length 2 the second node i can choose in 1 ways
for path length 4 the second node i can choose in 2 ways
for path length 6 the second node i can chosse in 4 ways

total number of ways i can choose two node is 64 ways (In probability, "choosing independently" means that the outcome of one event does not affect the outcome or probability of another event)

Expectation is Σ x*P(x) = 4.25

---

The direct formula for this type of question

2*h - 2 + 2^1-h

here h = height of binary tree

Answer 3

This is a very beautiful question on set theory and cartesian product.

I hope my solution explains why the asnwer is 4.25

Comments

nice👍

---

Thanks

Answer 4

Path can only have distinct vertices. If two leaves are same , path cannot be defined between them. distance(a,b) is not defined if a and b are same vertex.

This answer is according to definition of path given in two books which I came across:

1. Anaytics combinatorics by Alan Tucker

http://noahc.me/Applied%20Combinatorics%206th%20edition.pdf

page 4

2. Graph theory by Frank Harary.

https://shyam.nitk.ac.in/Books/GT%20Books/Harary.pdf page 13

3. mit book on discrete maths

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf page 384-385

see the comment below by ahabnnc

 

 

Comments

This seems legit. You should definitely challenge.

---

I am sorry, but i checked your references now. I don't think this makes much sense:

2. Graph theory by Frank Harary.

https://shyam.nitk.ac.in/Books/GT%20Books/Harary.pdf page 13

On the next page, page 14, it mentions :

Also,

3. mit book on discrete maths

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf page 384-385, 

 

On page 385, it mentions :

 

Answer 5

Ans should be 4.25,Becoz path length 0 is also possible as it is not said "distinct leafs"

Comments

But that way, we end up having two names for one node! That is contradictory.

---

@Arjun Sir, might it be the case, that the term independent is used to imply that, given a selection of node, post selection, the selection of the next node has nothing to do with the sub-tree from which the earlier node is chosen?

---

I think "Independent" only means that the "order of selection" is irrelevant. That is, we need to take into consideration only the "combination" and not the "permutation".

Answer 6

Choose any two leaves at random where first leaf is 'a' and second leaf 'b'. As it is mentioned 'independently' both the chosen leaves could be same and in that case path length = 0.

Now to find the expected path length, we have to

= $\frac{\sum\ pathLen\ *\ 8\ *\ pathsPerLeaf} {\sum TotalNoOfPaths} $

= $\frac{0*(8*1) + 1*0 + 2*(8*1) + 3*0 + 4*(8*2) + 5*0 + 6*(8*4)}{8*1+8*1+8*2+8*4}$

= 272/64 = 4.25

Comments

why u multiplied 8 with path length?

---

because there are 8 leaves.

---

for path length 6, u r getting paths per leaf =4

But I am getting 8 

Can u plz draw it?

a and b can be same leaf too

right?

---

Yes, a and b can be the same leaf too but for that, I've already considered it in the very first case where pathLength = 0. See the below pic :