The Gateway to Computer Science Excellence
+10 votes
5.6k 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 Veteran (425k points)
edited by | 5.6k views
+4
4.25
0
Will there be range for answer?
+2
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?
+9
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

7 Answers

+37 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 Veteran (425k points)
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?
+4
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
+21 votes
4.86 was what i got
by Junior (657 points)
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 Active (2k points)
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 Junior (577 points)
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".
+7 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 (121 points)
0
precise basic answer. Thanks.
+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 Loyal (9.8k points)
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 Junior (927 points)
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.

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
50,644 questions
56,531 answers
195,622 comments
101,340 users