K’th Largest Element in BST

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

Solution: Maintain the rank of each node

If we do an inorder traversal of a binary search tree, we can get an ascending sorted order. If we reverse the inorder traversal, we can get a descending sorted order. While doing the traversal, we keep track of nodes visited so far.

int BinarySearchTree::kthLargestUtil(TreeNode *root, int k, int &c) {
    if (!root || c > k) return INT_MIN;

    int result = kthLargestUtil(root->right, k, c);
    if (c == k) return result;

    c += 1;
    if (c == k) return root->val;

    result = kthLargestUtil(root->left, k, c);
    if (c == k) return result;

    return INT_MIN;
}

int BinarySearchTree::kthLargest(TreeNode *root, int k) {
    // Init the count of node visited as 0
    int c = 0;
    return kthLargestUtil(root, k, c);
}