Find the kth smallest or largest value in a BST
A ranking service keeps player ratings in a binary search tree. The leaderboard asks for things like “the 3rd lowest rating” (to show who is about to be relegated) and “the 1st highest rating” (the champion). Pages only ever show the top or bottom few entries, so a lookup should touch as few nodes as it can.
Each node looks like this:
{ value, left, right } // left and right are nodes or null
The tree is a valid binary search tree with unique values: every value in a node’s left subtree is smaller than the node’s value, and every value in its right subtree is larger. The tree is not necessarily balanced.
Implement findByRank(root, k).
findByRank(root, k) // => value, or null
k returns the k-th smallest value: k = 1 is the minimum.k returns the |k|-th largest value: k = -1 is the maximum.null when root is null, when k is 0, or when |k| is larger than the number of nodes..value of as few nodes as possible. Collecting the whole tree into an array first is too slow for the tests, which count how many values you read.// 50
// / \
// 30 70
// / \ \
// 20 40 85
// /
// 80
findByRank(root, 1); // => 20
findByRank(root, 3); // => 40
findByRank(root, -1); // => 85
findByRank(root, -2); // => 80
findByRank(root, 7); // => 85
findByRank(root, 8); // => null (only 7 nodes)
findByRank(root, 0); // => null
findByRank(null, 1); // => null