Search code examples
algorithmdata-structurestraversaltree-traversal

Median of BST in O(logn) time complexity

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 achieve the same using O(logn) time? The same has been asked here - http://www.careercup.com/question?id=192816

Solution

  • If you also maintain the count of the number of left and right descendants of a node, you can do it in O(logN) time, by doing a search for the median position. In fact, you can find the kth largest element in O(logn) time.

    Of course, this assumes that the tree is balanced. Maintaining the count does not change the insert/delete complexity.

    If the tree is not balanced, then you have Omega(n) worst case complexity.

    See: Order Statistic Tree.

    btw, BigO and Smallo are very different (your title says Smallo).