Amazon | Virtual Onsite

Given a complete binary search tree in the form of level-order traversal array, find the kth greatest value for a given key.
eg:

                                 10       
                               /    \
							  5      15
						    /   \   /  \
						   3     8 12   17

Input: arr = [10, 5, 15, 3, 8, 12, 17], key = 3, k = 2
Output: 8
N <= 10^8
1 <= K <= 20

Complexity expected - Less then O(N)