###### Digital-Logic-Design

October 15, 2023###### Mathematical-Reasoning

October 15, 2023# Binary-Trees

Question 46 |

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

5.54 | |

1.34 | |

4.25 | |

3.82 |

Question 46 Explanation:

There can be 8 paths between any 2

A node can be chosen twice and the path from that node to itself will be zero.

∴ Path 1 = 0

Similarly,

Path 2 = 2

Path 3 = 4

Path 4 = 4

Path 5 = 6

Path 6 = 6

Path 7 = 6

Path 8 = 6

∴ Expected value = Σ Path length × Probability of selecting path

= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8

= 1/4 + 1/1 + 3/1 + 0

= 4 + 1/4

= 17/4

= 4.25

__uniformly & independently__chosen leaf nodes.A node can be chosen twice and the path from that node to itself will be zero.

∴ Path 1 = 0

Similarly,

Path 2 = 2

Path 3 = 4

Path 4 = 4

Path 5 = 6

Path 6 = 6

Path 7 = 6

Path 8 = 6

∴ Expected value = Σ Path length × Probability of selecting path

= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8

= 1/4 + 1/1 + 3/1 + 0

= 4 + 1/4

= 17/4

= 4.25

Correct Answer: C

Question 46 Explanation:

There can be 8 paths between any 2

A node can be chosen twice and the path from that node to itself will be zero.

∴ Path 1 = 0

Similarly,

Path 2 = 2

Path 3 = 4

Path 4 = 4

Path 5 = 6

Path 6 = 6

Path 7 = 6

Path 8 = 6

∴ Expected value = Σ Path length × Probability of selecting path

= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8

= 1/4 + 1/1 + 3/1 + 0

= 4 + 1/4

= 17/4

= 4.25

__uniformly & independently__chosen leaf nodes.A node can be chosen twice and the path from that node to itself will be zero.

∴ Path 1 = 0

Similarly,

Path 2 = 2

Path 3 = 4

Path 4 = 4

Path 5 = 6

Path 6 = 6

Path 7 = 6

Path 8 = 6

∴ Expected value = Σ Path length × Probability of selecting path

= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8

= 1/4 + 1/1 + 3/1 + 0

= 4 + 1/4

= 17/4

= 4.25

Subscribe

Login

0 Comments