Median of BST in O(logn) time complexity

algorithm data-structures traversal tree-traversal
Harish picture Harish · Aug 18, 2010 · Viewed 7k times · Source

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

Answer

Aryabhatta picture Aryabhatta · Aug 18, 2010

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).

Related questions

Finding Preoder from Just Inorder Traversal?

I ran into a Mid-Exam Question, that took 4 days ago, I couldent underestand it! Suppose we have the answer given when we have an inorder traversal of a tree then how come we will find out the solution in case …

Read More
How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More