The Gateway to Computer Science Excellence
0 votes
1.1k views
From a complete binary tree T of 8 leaf nodes, two leaf nodes a and b are selected randomly and uniformly. What is the expected distance between a and b in T?
in Programming by Active (2.3k points) | 1.1k views
+5
4.85?
0
I got the same answer
0
got 4.84 :(
0
I also got 4.84.  And I can't remember how. Is there any chance it can lie in the given range?
0
34/7
0
I think in these type of problems , they keep some range
0
My answer comes 4.35. What will be the range in max case??
0
34/8.
0
How many marks was this question for?

2 Answers

+1 vote
distance   |    number of cases

2                       4

4                       8

6                       16

 

expectation = (2*4 + 4*8 + 6*16)/28
by (373 points)
0 votes
And:-34/7
by Active (2.7k points)
0
please don't ans like this
+2
i can answer if someone confirm 34/8 not 7 as 8 leaf ..... but i want confirm i am 50 -50
0
leaf are selected from total nodes??
0
N is 8 leaves

One leaf with 2 edge distance .

Two leaves with 4 edge distance

Four leaves with 6 edge distance.

Expectation = (1*2 + 2*4 + 4*6)/N = 34/8 = 4.25 (upto decimal places exact as stated in question)
0
I had a big doubt regarding this question what actually they want from us it said that randomly two leaves are selected so expected length of what ,irrespective of the fact since they are talking about leaves only length must remain 6 only . May be i am ,without thinking answering it but since it is cbt (8 leaves is sufficient to say total 15 nodes )and we all know leaves are at bottom why would path length will change it will remain constant. Please tell me my flaws in this regard .
0
What if the two leaves chosen between which edge distance needs to be calculated turn out to be same node ?

I think for that reason it's 34/8 not 34/7.
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,737 questions
57,324 answers
198,405 comments
105,169 users