## Interview Question

- 0of 0 votes
Median of BST in O(logn)

This is perhaps not a vague question afterall... Its beauty is in its shortness.

Here's what I'd say, hopefully correct:

a = extract_min ( BST );

b = extract_max ( BST );

print "Median = ", sqrt(a*a + b*b), ", Mean = ", (a + b)/2.0;

What do you say?

This is vague question. Besides the key, can we store nodes count in the tree nodes? If no more facilitation provided, no way to figure out the median in O(logn) IMHO.

- hunt September 22, 2009