A full binary tree of height 4 has 15 nodes

The 8 nodes at the bottom of the tree are called end nodes or leaf nodes. Two distinct end nodes are uniformly chosen. The expected length of the shortest path between them can be expressed as a/b, where a and b are coprime positive integers. What is the value of a+b?

0
0 0
0 0 0 0
00 00 00 00

To determine the expected length of the shortest path between two randomly chosen leaf nodes in a full binary tree of height 4, we need to calculate the probability of each possible path length and then multiply it by the corresponding path length.

A full binary tree of height 4 has 15 nodes in total, as mentioned in the question. The 8 nodes at the bottom are the leaf nodes, or end nodes. These are the nodes we are interested in.

To calculate the probability of each possible path length, we need to determine the total number of paths of each length and divide it by the total number of possible pairs of leaf nodes.

Let's start with the probability of a path length of 0. Since a path length of 0 means the two chosen nodes are the same, there is only one possible pair that meets this condition. So the probability of a path length of 0 is 1 divided by the total number of possible pairs, which is 8C2 (8 choose 2).

Next, let's calculate the probability of a path length of 1. In a full binary tree, there are 4 pairs of nodes that are adjacent to each other and hence have a path length of 1. So the probability of a path length of 1 is 4 divided by 8C2.

For a path length of 2, there are 4 pairs of nodes that are two steps away from each other, so the probability is 4 divided by 8C2.

Finally, for a path length of 3, there are no pairs of nodes in a full binary tree of height 4 that have a path length of 3. Therefore, the probability of a path length of 3 is 0.

Now, let's calculate the expected length of the shortest path. This can be done by multiplying each path length by its corresponding probability and summing them up.

Expected length = (0 * probability of path length 0) + (1 * probability of path length 1) + (2 * probability of path length 2) + (3 * probability of path length 3)

Let's do the calculations:

Probability of path length 0 = 1 / (8C2) = 1 / 28
Probability of path length 1 = 4 / (8C2) = 4 / 28
Probability of path length 2 = 4 / (8C2) = 4 / 28
Probability of path length 3 = 0

Expected length = (0 * 1 / 28) + (1 * 4 / 28) + (2 * 4 / 28) + (3 * 0) = 0 + 4/28 + 8/28 + 0 = 12/28 = 3/7

The expected length of the shortest path between two randomly chosen leaf nodes is 3/7.

To find the sum of a and b, we add the numerator and denominator:

a + b = 3 + 7 = 10