Solution: Find kth Maximum Value in Binary Search Tree

Statement

Given the root node of a binary search tree and an integer value k, return the $k^{th}$ maximum value in the tree.

Constraints:

• The number of nodes in the tree is n.

• $1 \leq$ k $\leq$ n $\leq 500$

• $0 \leq$ Node.data $\leq 10^4$

Solution

For this solution, we will recursively perform the inorder traversal (right subtree, root, left subtree) on the binary search tree. We will use the inorder traversal to get elements in sorted order.

While performing the inorder traversal on the tree, decrement $k$ by 1, indicating the number of maximum elements that still need to be found. After decrementing $k$, we check whether the value of $k$ has reached $0$. If it is $0$, we return the current node, indicating the node having the $k^{th}$ maximum element. If not, continue the traversal.

This approach ensures that we traverse the tree in a depth-first manner while appropriately updating k and effectively finding the $k^{th}$ maximum element.

Now, let’s look at the following illustration to get a better understanding of the solution: