Unicorns VO Coding Interview Question: Kth Largest Element in a Binary Search Tree

Given a Binary Search Tree (BST) and a positive integer k, find the kth largest element in the Binary Search Tree.

For example, in the following BST, if k = 3, then the output should be 15, and if k = 5, then the output should be 4.

      10
     /  \
    4    20
   /    /  \
  2    15   40

This problem asks for the kth largest value in a BST. Because an in-order traversal of a BST yields values in ascending order, the key idea is to traverse in reverse in-order (right, root, left) so nodes are visited from largest to smallest. Once the kth node is reached, the answer can be returned immediately. This avoids storing all values and typically runs in O(n) time with O(h) extra space, where h is the tree height.