The Gateway to Computer Science Excellence

+23 votes

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) _________.

+1

Ma'am, naturally one will not think of taking the same nodes twice until he understands the emphasis on this very word. Though I recently realized it doesn't hv any effect on the ans.

Sorry Ma'am I think he/she is not that evil.

Sorry Ma'am I think he/she is not that evil.

0

wait...no...then it will be 8 x 7 and all will be divided by 56 instead of 64. Evil.

and ans will become 4.84

and ans will become 4.84

0

Total no of possible pairs will become 8 x 7 = 56.

First place 8 choices, second place 7 choices if they are dependent.

If taken as independent, first place 8 choices second place also 8 choices.

am I wrong?

First place 8 choices, second place 7 choices if they are dependent.

If taken as independent, first place 8 choices second place also 8 choices.

am I wrong?

+19

Yes. This question was putting emphasis on "independent" and that's what GATE always does -- whatever you learn must be proper even if you don't learn everything. Too much learning without understanding properly is useless for GATE.

+56 votes

Best answer

Two leaves

aandbofTare chosen uniformly andindependentlyat random.

See the word "independently" here. It means that choice of $a$ must not affect choice of $b$ and vice versa. This implies that both $a$ and $b$ can even be the same node.

Now, we are given that the binary tree has $8$ leaves. $\left(2^3 = 8\right) \implies$ we have $3$ levels in the tree starting from $0.$ The distance in terms of number of edges between **any two leaf nodes will always be even**. If we consider any two leaves (not necessarily distinct)

- No. of pairs with path length $0 = 8.$ (When $a = b)$
- No. of pairs with path length $2 = 8.$ (For each of the $8$ leaf nodes, we have a pair and since the selection is independent order of the pair is also significant)
- No. of pairs with path length $4 = 16.$ (For each leaf node we have to go two levels up and while coming down we have $2$ choices. So, we get $8 \times 2 = 16$ pairs)
- No. of pairs with path length $6 = 32.$ (For each leaf node we have to go till the root, and from there while coming down it has $2 \times 2 = 4$ choices. Thus we get $8 \times 4 = 32 $ pairs.

Total number of possible pairs $ = 8 \times 8 = 64$

So, expected path length

$\quad =0 \times \frac{8}{64} + 2 \times \frac{8}{64}+4 \times \frac{16}{64}+6 \times \frac{32}{64}= \frac{272}{64}=4.25$

+1

@Arjun sir kuch smjh nh Aya aapka solution mtlb kaise pair Lena h and all ,can u pls explain in other way .

0

The questions states that "2 nodes A and B are chosen". This mostly implies that A and B are distinct nodes. If this is the case, then the number of possible pairs would be $^{8}C_{2}$ = 28 (and not 64 as in your case). How would you justify this?

+6

Read the question it says "independently" means the selection of first node is independent of second node.Hence for both leaf node selection we have 8 choices hence total 64

+4

Let leaves are $a,b,c,d,e,f,g,h$

Path length $0:a-a,b-b,c-c....h-h=8$

Path length $2: a-b,b-a,c-d,d-c,e-f,f-e,g-h,h-g=8$

Path length $4:a-\fbox{n}-\fbox{n}-\fbox{n}-c$

$\underbrace{a-\fbox{n}-\fbox{n}-\fbox{n}-d}$

**a is having 2 choices after **

** reaching two levels up**

Similarly $'b'$ is having 2 choices

Similarly $'c'$ is having 2 choices: $c-\fbox{n}-\fbox{n}-\fbox{n}-a$

$\underbrace{c-\fbox{n}-\fbox{n}-\fbox{n}-b}$

.

.

$\therefore 8$ leaves each having $2$ choices $8\times 2=16$

Path length $6:$ $a-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-e$

${a-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-f}$

${a-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-g}$

$\underbrace{a-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-\fbox{n}-h}$

** a is having 4 choices after **

** reaching root **

Similarly $'b'$ is having 4 choices

Similarly $'c'$ is having 4 choices

.

.

$\therefore 8$ leaves each having $4$ choices $8\times 4=32$

+43 votes

A full binary tree of 8 leaves:

Let's say we take node H, the distances from H to all other nodes (including itself) would be:

H | I | J | K | L | M | N | O |

0 | 2 | 4 | 4 | 6 | 6 | 6 | 6 |

If another node is taken, a similar table (to the one above) is attained. Therefore, all nodes have the same distances when added together.

So, If a node is considered, the probability of choosing another node would be 1/8 (including itself - __independent choosing__].

Therefore, E = 1/8(0+2+4+4+6+6+6+6) = 4.25

+2

@vaishnavi30

In Probability, events can be dependent or independent of other events.

Let's say tossing a coin two times, the probability of getting heads in either trial is 1/2. This is an independent event, where the outcome of the next trial is not dependent on the previous.

Now take an example of 2 balls (one red, one blue). The probability of getting blue in the first pick is 1/2 and the second pick would be 1 (since red was picked last time and only blue remains). These are dependent events where the probabilities change depending on the previous outcome.

Back to this question, when it says independent choosing - for choosing two nodes and finding their distance, we could pick any node as the first (1/8 probability) and the second node as we may think would be (1/7) since we have already picked the first but that's just dependent choosing and not what the question is asking. **When we consider independent choosing, we can pick the first node again as the second node as well, therefore probabilities remain the same (1/8 => for both). **

Hope this helps

+21 votes

+11 votes

Path can only have distinct vertices. If two leaves are same , path cannot be defined between them. distance(a,b) is not defined if a and b are same vertex.

This answer is according to definition of path given in two books which I came across:

1. Anaytics combinatorics by Alan Tucker

http://noahc.me/Applied%20Combinatorics%206th%20edition.pdf

page 4

2. Graph theory by Frank Harary.

https://shyam.nitk.ac.in/Books/GT%20Books/Harary.pdf page 13

3. mit book on discrete maths

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf page 384-385

see the comment below by ahabnnc

+4

I am sorry, but i checked your references now. I don't think this makes much sense:

2. Graph theory by Frank Harary.

https://shyam.nitk.ac.in/Books/GT%20Books/Harary.pdf page 13

On the next page, page 14, it mentions :

Also,

3. mit book on discrete maths

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf page 384-385,

On page 385, it mentions :

+7 votes

0

Given that the question clearly mentions "a" and "b" as the names of the two nodes, this can also imply non superimposition of the nodes.

+4

sir but i have a doubt..

it's written that "two leaves a and b", so if both time the same leaf is chosen, they are not two leaves, they are the single leaf.. but there is this word independently.. i don't know, i'm just confused!!

it's written that "two leaves a and b", so if both time the same leaf is chosen, they are not two leaves, they are the single leaf.. but there is this word independently.. i don't know, i'm just confused!!

+1

@Arjun Sir, might it be the case, that the term independent is used to imply that, given a selection of node, post selection, the selection of the next node has nothing to do with the sub-tree from which the earlier node is chosen?

+5 votes

Choose any two leaves at random where first leaf is 'a' and second leaf 'b'. As it is mentioned 'independently' both the chosen leaves could be same and in that case path length = 0.

Now to find the expected path length, we have to

= $\frac{\sum\ pathLen\ *\ 8\ *\ pathsPerLeaf} {\sum TotalNoOfPaths} $

= $\frac{0*(8*1) + 1*0 + 2*(8*1) + 3*0 + 4*(8*2) + 5*0 + 6*(8*4)}{8*1+8*1+8*2+8*4}$

= 272/64 = 4.25

Now to find the expected path length, we have to

= $\frac{\sum\ pathLen\ *\ 8\ *\ pathsPerLeaf} {\sum TotalNoOfPaths} $

= $\frac{0*(8*1) + 1*0 + 2*(8*1) + 3*0 + 4*(8*2) + 5*0 + 6*(8*4)}{8*1+8*1+8*2+8*4}$

= 272/64 = 4.25

0 votes

I think answer is 4.596 assume a,b,c,d,e,f,g,h are at leave level in this order)

0 length =8(self people only) again because of two magical words (independent and uniform). since uniform irrespective of the fact any how probability of choosing two leaves is 1 so my concern is leaves only not internal node , I mean to say i will only choose from leaves not from any where

2 length =3 (a-a,a-b,b-b)(now if i choose c and b(no matter what 2 length is not there ,but 4 length is there(for this case it will be consider ,which i had covered latter)

4 length =10(a-a,a-b,a-c,a-d,b-b,b-c,b-d,------)(4+3+2+1) since unique path i ruled out those case in which a-b=b-a) some one might put up question what if i select b-a path rather then a-b (no matter what it will be unique path only, this is an assumption tell me if i am wrong here)

6 length=36(8+7---------1)

now expected length(average )=((36*6)+(10*4)+(3*2)+(0*8))/57=4.596~4.60 If I need correction please let me know. May be I have done blunder in this solution.

0 length =8(self people only) again because of two magical words (independent and uniform). since uniform irrespective of the fact any how probability of choosing two leaves is 1 so my concern is leaves only not internal node , I mean to say i will only choose from leaves not from any where

2 length =3 (a-a,a-b,b-b)(now if i choose c and b(no matter what 2 length is not there ,but 4 length is there(for this case it will be consider ,which i had covered latter)

4 length =10(a-a,a-b,a-c,a-d,b-b,b-c,b-d,------)(4+3+2+1) since unique path i ruled out those case in which a-b=b-a) some one might put up question what if i select b-a path rather then a-b (no matter what it will be unique path only, this is an assumption tell me if i am wrong here)

6 length=36(8+7---------1)

now expected length(average )=((36*6)+(10*4)+(3*2)+(0*8))/57=4.596~4.60 If I need correction please let me know. May be I have done blunder in this solution.

52,345 questions

60,498 answers

201,865 comments

95,323 users