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

One of the toughest and trickiest questions in gate 2019

---

One silly question is why the total number of alternative paths is 8^2, rather than 2^8.

It's similar to n places with the m option → n^m

that is 8 places with 2 option → 8^2

 

---

Question Says total 8 leaves ,

1.) First choose any 2 leaves independently and Uniformly=(1/8)*(1/8)=1/64.

2.) Use logic of Expectation.

{1/64 (2+4+4+6+6+6+6+4+4+6+6+6+6+2+6+6+6+6+6+6+6+6+2+4+4+4+4+2)}*2 (Multiply 2 because Node a and b can be swapped also so Total 2! ways.

2.125*2=4.25...

Answer 1

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 : 

Answer 2

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👍

Answer 3

 

Forgive me for bad handwriting.

Answer 4

I think answer is 4.596 assume a,b,c,d,e,f,g,h are at leave level in this order)

0 length =8(self people only) again because of two magical words (independent and uniform). since uniform irrespective of the fact any how probability of choosing two leaves is 1 so my concern is leaves only not internal node , I mean to say i will only choose from leaves  not from any where  

2 length =3 (a-a,a-b,b-b)(now if i choose c and b(no matter what 2 length is not there ,but 4 length is there(for this case it will be consider ,which i had covered latter)

4 length =10(a-a,a-b,a-c,a-d,b-b,b-c,b-d,------)(4+3+2+1) since unique path i ruled out those case in which a-b=b-a) some one might put up question what if i select b-a path rather then a-b (no matter what it will be unique path only, this is an assumption tell me if i am wrong here)

6 length=36(8+7---------1)

now expected length(average )=((36*6)+(10*4)+(3*2)+(0*8))/57=4.596~4.60 If I need correction please let me know. May be I have done blunder in this solution.

Comments

What do we mean by path length here?
How can a path be of length 0, especially when we are going to leaf nodes?

I cannot understand this at all.