gate 2019

Question

From a complete binary tree T of 8 leaf nodes, two leaf nodes a and b are selected randomly and uniformly. What is the expected distance between a and b in T?

Comments

4.85?

---

I got the same answer

---

got 4.84 :(

---

I also got 4.84.  And I can't remember how. Is there any chance it can lie in the given range?

---

34/7

---

I think in these type of problems , they keep some range

---

My answer comes 4.35. What will be the range in max case??

---

34/8.

---

How many marks was this question for?

Answer 1

distance   |    number of cases

2                       4

4                       8

6                       16

 

expectation = (2*4 + 4*8 + 6*16)/28

Answer 2

And:-34/7

Comments

N is 8 leaves

One leaf with 2 edge distance .

Two leaves with 4 edge distance

Four leaves with 6 edge distance.

Expectation = (1*2 + 2*4 + 4*6)/N = 34/8 = 4.25 (upto decimal places exact as stated in question)

---

I had a big doubt regarding this question what actually they want from us it said that randomly two leaves are selected so expected length of what ,irrespective of the fact since they are talking about leaves only length must remain 6 only . May be i am ,without thinking answering it but since it is cbt (8 leaves is sufficient to say total 15 nodes )and we all know leaves are at bottom why would path length will change it will remain constant. Please tell me my flaws in this regard .

---

What if the two leaves chosen between which edge distance needs to be calculated turn out to be same node ?

I think for that reason it's 34/8 not 34/7.