The Gateway to Computer Science Excellence
+23 votes
8.9k views
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) _________.
in DS by
edited by | 8.9k views
+4
4.25
0
Will there be range for answer?
+6
What an Evil person who put the "Independent" keyword in there.
+1
why?without independent what will be ans?
+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.
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
0
Any reference?
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?
+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.
0
Right sire.
0

So finally the guy is evil. :D 

@ShamikBanerjee

0
So one has to read the question very carefully with all the time pressure, else they would gloss over "independent"...
0
yes
0

Can 4.00 be the answer?

8 Answers

+56 votes
Best answer

Two leaves a and b of T are chosen uniformly and independently at 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$

by
edited by
0
can a "path" be of length 0?
0
In first case only one node is selected.
+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
0
no of pairs with path length 2 = 8 how????
0
My solution was given only for answer key purpose. I'll explain in detail soon.
+1

@Arjun sir , more explanation is needed here. How did u get these pairs?

0
can anyone please explain how the pairs are taken of path length 0, path length 1 and all others
+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$

0

@Arjun

Sir what will be the case when a and b are dependent. I understand that in this case total number of possible pairs will be 8 X 7 = 56, and there will be no case of path length 0.

But will it affect other cases like pairs of path length 2, 4 and 6. Is there any changes in that?

 

+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

 

 

 

 

by
+1
precise basic answer. Thanks.
+3
Thank you for your effort in drawing diagram and creating most simple and straighforward answer
+1
One picture/figure remove all difficulties. Great explanation.
+1
What does independently means?plz explain
+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

+1
Yes, I got it.

Thanks for explanation
+1
jiko:)
+21 votes
4.86 was what i got
by
0
me too. (2+4+4+6+6+6+6)/7= 34/7= 4.86
0
Same i got 4.86...
0
i also got 4.85

(2*4+4*8+6*16)/28
+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

 

 

by
edited by
+2
This seems legit. You should definitely challenge.
+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
Ans should be 4.25,Becoz path length 0 is also possible as it is not said "distinct leafs"
by
edited by
+2
Distinct can be implied; but they have mentioned "independently" :)
0
ok sir...is the ans correct(4.25)
0
But then you will end up choosing only 1 leaf
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!!
0
two leafs hi honge bus wo same honge
0
okkk... right... 2 more marks gone due to this independent keyword:(
0
But that way, we end up having two names for one node! That is contradictory.
+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?

0
I think "Independent" only means that the "order of selection" is irrelevant. That is, we need to take into consideration only the "combination" and not the "permutation".
+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
by
0
why u multiplied 8 with path length?
0
because there are 8 leaves.
0

for path length 6, u r getting paths per leaf =4

But I am getting 8 

Can u plz draw it?

a and b can be same leaf too

right?

+4

Yes, a and b can be the same leaf too but for that, I've already considered it in the very first case where pathLength = 0. See the below pic : 

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.
by
0
What do we mean by path length here?
How can a path be of length 0, especially when we are going to leaf nodes?

I cannot understand this at all.
0 votes

 

Forgive me for bad handwriting.

ago by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,498 answers
201,865 comments
95,323 users