nightmare final question

[Keerthikanth Kodali]

is it really possible to find kth largest element in  less than 0(n) in balanced binary search tree?

[Jeff Heidel]

I think so,
Since it is a binary search tree, an inorder traversal should give you a sorted list, and a reverse inorder traversal should give you a list sorted in descending order.
Simply stop the traversal once you have reached the desired kth element, and you've found the kth largest element without exploring all n nodes.

Somebody please correct me if this is wrong.

[Robert Escriva]

On Fri, May 13, 2011 at 12:52:36PM -0400, Keerthikanth Kodali wrote:
> is it really possible to find kth largest element in less than 0(n)
> in balanced binary search tree?

In short: yes.

A BST maintains sorted order. Given that the height is bounded by O(log
n), we know that the tree is balanced. If you do an in-order traversal,
you'll visit O(k + log n) nodes. When k is considered fixed (e.g.,
you'll always want element 5, no matter how many elements are in the
tree), the complexity of the algorithm is indeed better than O(n).

-Robert

[Holly Domke]

I think it's possible but with a slightly different method, as if k = n, you have to explore them all. 

If k < n/2, the process is the same as Jeff described, but only on the left subtree. If k = n/2, return the root. And if k > n/2, run in order traversal on the right subtree and stop on k-(n/2). 

Also, correct me if I'm wrong.

--
Holly Domke

Cornell University - 2014

College of Engineering - Information Science, Systems, and Technology

662-380-3749

[Keerthikanth Kodali]

HI Robert,

When the question says we have to do less than 0(n) I assumed we have to do that in 0(log n).
and I thought its not possible in 0(log n)  and I gave a counter  example of how it can be more than 0(log n)
so now the question comes down to if 0(k+log n) == 0(logn) ?
Also do you think any partial credit??

Thanks,
-Kant

[Todd Warszawski]

How does the h = O(log(n)) ensure balancing?  Since it is big O, couldn't this mean that the height is greater than log(n) as long as there is some constant multiple of log(n) that the height stays below, such as if the shortest distance from the root to a leaf was always half the longest distance from the root to a leaf?  Is it still possible to run the algorithm in better than linear time if the tree is not perfectly balanced?

Also, will we ever get a chance to see the solutions?

Thanks,

Todd

[Nikos Karampatziakis]

You are right Todd. A height of O(log(n)) means the tree is very
roughly balanced but still not pathologically unbalanced. A good
example of such trees are red-black trees. The solution works in
O(h+k) where h is the height of the tree. It will be released together
with your grades.

-Nikos