GATE Computer Science (CS) 2019 Solved Papers

Question : 56 of 65

Marks: +1, -0

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}

{T}

(i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _________.

Your Answer:

Validate

Solution:

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

Go to Question:

Prev Question

Next Question