# Average number of comparisons to locate item in BST

This is a GRE practice question. If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?

(A) 1.75

(B) 2

(C) 2.75

(D) 3

(E) 3.25

My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!

• Chosen at random according to what distribution? *sigh* It makes me sad when you have a whole country where getting an advanced degree depends on passing an exam that's set by an organization that doesn't know the difference between "at random" and "uniformly at random". – David Richerby Aug 13 '15 at 8:10
• @DavidRicherby Also, they can't draw trees. The image clearly shows a graph with a 4-cycle of node $E$, $C$, $H$ and $DF$. – Raphael Aug 13 '15 at 11:27
• Re-reading this, let me note that the approach is wrong because it a) confuses average and worst-case and b) assumes a (tight) $\lg n$ bound that does not hold. – Raphael Aug 13 '15 at 11:29
• @DavidRicherby Of course. I was trying to make a joke. – Raphael Aug 13 '15 at 11:37

Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then $$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$ where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.

• Working out the math for A.Schulz's answer (4*2+3*3+(2*2)+1)/8=2.75. Ie takes 1 comparison to find E, 2 comparisons to find C and H, etc.. – Philip Menke Oct 22 '14 at 1:42

Find comparisons for every element and total them ie; 22 comparisions for 8 elements so for 1 element 22/8=2.75

• That only works for the uniform distribution, and adds nothing over the current accepted answer. – Raphael Aug 13 '15 at 7:15
• @Raphael The accepted answer does not actually give the result, but kind of explain, much too abstractedly for my (pedagogical) taste, how to compute it. The answer is there, by in someone else's comment which does not count. Actually, I was bothered by the question because I do not know what counts as a comparison. I still do not really know. Is it ignorance on my part, or lack of precision in question and answers? – babou Aug 13 '15 at 10:30
• Your answer is credible. But you do not give enough details on why you do it that way. An answer that is too brief does not help readers to really understand. And if you were just applying the formula of the previous answer, you should say so explicitly. – babou Aug 13 '15 at 10:35
• @babou Every community member can propose an edit to the accepted answer, extending it by the concrete example from the comment. – Raphael Aug 13 '15 at 11:26

1 node at level 1 {E} 2 node at level 2 {C H} 3 node at level 3 {B D F } 2 node at level 4 {A G} 1*1+2*2+3*3+2*4=22 22/8=2.75(ANS)

• The question asks for an explanation, not a calculation: anyone who understands the concepts should be able to do the calculation on their own. We already know that the answer is 2.75 because that's stated in the question. – David Richerby Jun 16 '15 at 10:57