Gate2019 cs Q56

56Let 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 (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________.

Note – Numerical Type question

Option : A
Explanation :
No. of pairs with path length 0=8.0=8.
No. of pairs with path length 1=0.1=0.
No. of pairs with path length 2=8.2=8.
No. of pairs with path length 3=0.3=0.
No. of pairs with path length 4=16.4=16.
No. of pairs with path length 5=0.5=0.
No. of pairs with path length 6=32.6=32.
Total number of possible pairs =8×8=64=8×8=64
So, expected path length,E(x),
=0×864+2×864+4×1664+6×3264=27264=4.25

Forgot your password?

I agree with the Terms.