I came across solution given at http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8 using Morris InOrder traversal using which we can find the median in O(n) time.
But is it possible to acheive the same using O(logn) time? The same has been asked here - http://www.careercup.com/question?id=192816