The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
618 views
What was  the Expectancy in the full binary tree question asked in the exam ?

I got 3
asked in GATE by Active (1.2k points) | 618 views

3 Answers

+3 votes
I think the answer is 34/8 = 4.25.

Question: From a complete binary tree T of 8 leaf nodes, a and b are selected randomly and independently. What is the expected distance between a and b in T.

Here is how I solved it:

Since, the two leaf nodes are selected independently, both nodes can be same. If the leaf nodes are numbered 1 to 8 from left to right, then,

I can reach 1 node (i.e., same node) in a distance = 0

I can reach 1 node in a distance = 2

I can reach 2 nodes in a distance = 4

I can reach 4 nodes in a distance = 6

So, expected distance = (1 * 0 + 1 * 2 + 2 * 4 + 4 * 6)/(1 + 1 + 2 + 4) = 34/8.
answered by (57 points)
+2 votes
4.85=34/7
answered by Active (1.2k points)
0
Which seven cases you considered
0
For each leaf node, there were 7 other leaf nodes
0
But the question was about the distance in between the two nodes at the same level
0
Yes, all leaves are at same level, and they asked path length
0 votes
I got the answer as 5.0
answered by (187 points)
0
Anyone else please confirm our answer
0

I solved it as follows

Related questions

0 votes
1 answer
2
+5 votes
5 answers
3
0 votes
2 answers
4
0 votes
0 answers
6
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,069 questions
53,206 answers
184,550 comments
70,420 users