CareerCup

An O(log n) worst case lower bound is impossible. Consider the case where the tree is unbalanced to the point where it's one large completely-left or completely-right list. Now say k = n. In this case, no matter what strategy you use, you will have to traverse k = n nodes (no way to jump ahead in what is really a linked list).

Assuming that BST is balanced, the root of the tree is N/2 element (median). If location K == N/2, then we have found the match. If greater use the same logic recursively on right subtree, else left subtree.

I think you don't need to traverse the entire tree. Just use a counter as you traverse from the end element, increment the counter by one while you are traversing each element and retune the element when the counter == K.
reach the end elment O(logN), find the Kth element O(K), so it's O(K+logN)

How about inorder traversal of BST and then look for kth element from the end.

The solution is easy to guess when it is a balanced tree as shown above. However, I think that with tree not balanced, one has to keep information at each node e.g. Node A tell us how many nodes there are in left sub-tree and right sub-tree. With this information in mind, we can go forward and right an traversal on O(log N). In case of balanced tree this information is not required as at every node, it is easy to predict the number of nodes in left and right sub-tree.

Please suggest some better solution that does not use this knowledge and still finds the solution in O(log n)

Do iterative in-order and process first K nodes using stack1.Do the iterative in-order for this one and the entire tree(use stack2). When there are no more elements in stack1 (or u finished processing the tree) return the value which has to be processed in stack2...This would be the Kth maximum element...

Something like Inorder but with a twist ;-)

Recursively traverse right/root/left in the BST.
This way you will be travelling in descending order (unlike INORDER which is ascending).

Keep a counter and increment on each find until it reaches K.

worst case complexity will be O(N)

BST is not guaranteed to be a balanced here

@Anon . I think that even in worst case it would be a sorted linked list and then you can balance in O(logN) and find the K'th maximum again (probably in O(log N)

Its good to build a array of pointers, which keep the nodes in sorted order.
One time building cost for this array is O(n), but later for accessing purpose its cost became O(1) "constant".

it is not possible to find the kth maximum element in BST in O(logN) time...

I believe that the BST needs to be changed a little bit. For each node, an integer is added to track the elements in the subtree starting from that node. This is NOT hard because you need to go throught that node when adding a node to the BST.

That way, you can know where you should go smartly. Without this, you always have to transverse the BST tree.

Associate weight(Wt) with each node, like root's Wt will be no of (left sub tree+ right sub tree+1)...similarly for each node. during tree formation...or else call a utility to give no of nodes. based on that determine whether if(N==Wt of node+1) return node, else if(N>Wt of left sub tree+1) recursively traverse right sub tree else traverse left sub tree

Friends, I am not sure if the trick I describe would work, but it 'sounds' promising/interesting to me:

1) Use 2 pointers starting at root and traverse the tree in reverse-inorder (right-root-left).
2) The pointers not k steps but are log2(k) apart.
3) Basically call MAXIMUM(tree) procedure twice and return the key of the delayed pointer when the first pointer reaches real max value.

Am I making sense?

I think solution will involve having two more data in each node , leftHeight , rightHeight , This way solution is trivial

O(logN) solution is impossible with BST, If you have a balanced tree then in that case you might get such solution.

start with the min element (you motherfuckers know how to do that right?) keep finding the inorder successor for k times. morons...

go root->right recursively till u reaches last node. That will be max element.
start finding its predecessor to K-1 times.

O(log n) is impossible to achieve with BST unless it is balanced like AVL tree or red-black tree. If it is balanced then you can find the k-th minimum in O(log n) time using order statistic tree...similarly just by reversing you ca get the k-th maximum in O(log n) time but i repeat for BALANCED TREE only.