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);
}