borrow the way of splitting array in quicksort, which can achieve O(n) time in average for any k. The more detail of this algorithm is: select a pivot value, and split the array into three parts. The elements in the first part are less or equal to the pivot value or empty, the second part is one element which is equal to the pivot, and elements in the last part is great them the pivot value or empty. If the index of the second part element is equal to k, then just return it, else if it is greater than k, then go to split the first part recursively, else go to split the third part recursively.

binary tree would not work unless it was balanced and even then searching for the kth highest node would be overly complex. Better answer - Perform k iterations of a bubble sort. Run time would be O(kn). To prevent O(n^2) (k ~ n) reverse bubble sort if k > n/2.