Challenge: Find kth Maximum Value in a Binary Search Tree
Given the root to a binary search tree--a number "k"--write a function to find the kth maximum value in that tree. A solution is placed in the "solution" section to help you, but we would suggest you try to solve it on your own first.
We'll cover the following
Problem Statement
In this problem, you have to implement the findKthMax()
function to take a BST and any number “k” as an input, and return kth maximum number from that tree. An illustration is also provided for your understanding.
Function Prototype
int findKthMax(Node root, int k);
Here, root is the root node of the Binary Search Tree and k is an integer number.
Output
It returns the kth maximum value from the given tree.
Sample Input
bst = {
6 -> 4,9
4 -> 2,5
9 -> 8,12
12 -> 10,14
}
where parent -> leftChild,rightChild
k = 3
Sample Output
10
Explanation
As “k” equals 3, we need to find the 3rd maximum value from the given tree. The maximum value in the tree is 14, while 12 is the second-maximum, which leaves us with our required value 10 as the third-maximum value in the given tree. Here’s an illustration of the given challenge:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.