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

Expectation = Summation(Output*Probability of Output)

→ Now for output 0 : Chose any node first, but for 2^nd ,you have only 1 choice out of 8,that is the same node,so probability =(1/8)

→ Now for output 2 : Chose any node first, but for 2nd ,you have only 1 choice out of 8,that is the node beside it,so probability =(1/8)

→ Now for output 4 : Chose any node first, but for 2nd ,you have only 2 choices out of 8,which are the 2 nodes at distance 4 from it,so probability =(2/8)

→ Now for output 6 : Chose any node first, but for 2nd ,you have only 4 choices out of 8,which are the 4 nodes at distance 6 from it,so probability =(4/8)

=Summation(0*(1/8) + 2*(1/8) + 4*(2/8) + 6*(4/8)) = 34/8 = 4.25