Nth largest node in a BST

Find the Nth largest node in a BST.


Example BST:

Code input/output:


inorder: 

1 3 4 6 7 8 10 13 14 
Size of BST: 9
1 largest node: 1
2 largest node: 3
3 largest node: 4
4 largest node: 6
5 largest node: 7
6 largest node: 8
7 largest node: 10
8 largest node: 13
9 largest node: 14

Rank of a node in a Order Statistic Binary Tree

You have a binary tree where each node knows the number of nodes in its sub-tree (including itself). Given a node n and an int k, write a function to return the kth node in an in-order traversal. Can you do this non-recursively?

Retrieving an element with a given rank from a Binary Search Tree in O(logN) time.

The given Binary Search Tree has an extra information in each of its node.
Each node of the BST contains a field called "size", which is the number of internal nodes in
the subtree rooted at node (including node itself).

Kth Smallest element in an array in O(N) average time.

Given N elements in an array. Find the ith smallest element (element of rank i).