kth Largest Element in BST

Problem Statement

We are provided with a Binary Search tree and the task is to find the $k^{th}$ largest element in BST (Binary Search Tree).

Refer to the Example and Example Explanation sections for more details and the Approach section to understand how to find the $k^{th}$ largest element in bst.

Example

Example 1:

The given input binary search tree is:

The value of k is: 3

So, the $3^{rd}$ largest element comes out to be: 15.

Example 2:

The given input binary search tree is:

The value of k is: 2

So, the $2^{nd}$ largest element comes out to be: 30.

Example Explanation

Before getting into the explanation of the example and how to $k^{th}$ largest element in bst, let us first get a brief introduction about the binary search tree.

A binary search tree can be defined as a collection of objects or elements or entities known as nodes. These nodes are linked together to represent a hierarchy. The top node of the hierarchy is known as the root node. Each node of a binary search tree contains some data and it can have at most two child nodes. A root node can never have a parent node. The nodes that do not have any child nodes are termed leaf nodes.

The main property of a binary search tree is that the left child of a node must be less than the current node and the right child of a node must be greater than the current node.

Example:

Let us take the first example provided above, the given binary search tree is:

In the binary search tree mentioned above, we can see that 40 is the first largest element, 20 is the second largest element and 15 is the third ($k^{th}$) largest element of the bst.

Since the right subtree contains the larger elements, we must look at the right subtree first.

Refer to the Approach section, for more clarity and to understand the other approaches to find the $k^{th}$ largest element in bst.

Input/Output

• The first input is the root node of the binary search tree
• The second input is the value of k.
• The third input is the value of n, i.e. the number of nodes present in the bst.

Example:

The given input binary search is:

The given value of k is: 3 The given value of n is: 6

The output is:

Constraints

• 1 <= Number of nodes (n) <= $10^5$
• 1 <= Data of a node <= $10^5$

In some problems, you may find the number of test cases represented by t. So, we only need to call the findKthLargest() function t-times.

Approach 1: Naive Approach - Brute Force - using In-Order Traversal and Extra Space

The most basic approach to the problem - find the $k^{th}$ largest element in bst, we are going to traverse the entire binary search tree using the in-order traversal algorithm and side by side storing the values inside a data structure like an array or a list. Now, as we know that when we perform the in-order traversal of a binary search tree, we will get the nodes in ascending order (or increasing order) only.

So, we can perform the in-order traversal and keep on inserting the values into an array of sizes equal to the number of nodes of the binary search tree. Once the traversal is completed, we can simply return back the $n - k$ th index element from the array as the $k^{th}$ largest element in bst.

Before getting into the pseudo code and implementation, we should be familiar with the concept of in-order traversal. So, let us briefly discuss the in-order traversal of a binary search tree.

In the in-order tree traversal we first traverse the left subtree, then the root node, and finally the right subtree.

The pseudo-code for the in-order traversal can be:

1. If the current node has a left child, recursively visit the left subtree (until NULL is found).
2. Visit the root node.
3. If the current node has the right child, recursively visit the right subtree (until NULL is found).

Let us take an example tree to understand and visualize the in-order traversal better.

The final in-order traversal obtained will be: 4 2 5 1 3.

Algorithm

The pseudo-code for the above-discussed algorithm can be:

1. Initialize an array of size = n i.e. the number of nodes present in the binary search tree.
2. Start the in-order traversal of the binary search tree whose algorithm is discussed above. Now, in place of printing the current node's data, we will insert the current node's data into the array.
3. At last return the $a[n-k]$ element as the $k^{th}$ largest element in bst.

Code Implementation

Let us code the above-discussed algorithm for better understanding.

C++ code:

Java code:

Python code:

When the Input tree is:

And the given value of k is: 3

Output

In the brute force or basic approach to the problem - find the kth largest element in bst, we are traversing the input binary search tree only once using the in-order traversal of the binary search tree. We are using an extra array to store the node's data.

Time Complexity

Since we are traversing the input binary search tree only once, the time complexity of the brute force approach to the problem - find the kth largest element in bst comes out to be O(n), where n is the size of the input binary search tree.

Space Complexity

Since we are using an extra array to store the node's data, the space complexity of the brute force approach to the problem - find the kth largest element in bst comes out to be O(n), where n is the size of the array (same as the number of nodes of the bst).

Approach 2: Recursive Approach - using Reverse In-Order Traversal

Now as we have seen that we can use the in-order traversal and an array to find the kth largest element in bast, can we get our required answer without using the extra array? The answer is yes.

An efficient algorithm for the problem - to find the $k^{th}$ largest element in bst is to traverse the binary search tree in the reverse order using the in-order traversal. As we know that the in-order traversal of a binary search tree produces elements in increasing order. So, if we perform the reverse in-order traversal, we will get the elements in decreasing order.

Now, as we are performing the reverse in-order traversal, we need to keep track of several elements encountered which can easily be performed using a counter. So, when the counter reaches k we have found our kth largest element.

The reverse in-order traversal is simply traversing the right subtree then the root and finally the left subtree.

Algorithm

The pseudo-code for the above-discussed algorithm can be:

1. Initialize a counter variable that will count the number of elements encountered in the binary search tree.
2. Start the reverse in-order traversal of the binary search tree whose algorithm is discussed above. Now, in place of printing the current node's data, we will decrement the counter.
3. Before the left subtree call, we will check if the counter's value has reached k or not. If the counter's value is the same as k then we will return the value of the node's data. If the value of counter is less than k then we will continue the above-stated process.

Code Implementation

Let us code the above-discussed algorithm for better understanding.

C++ code:

Java code:

Python code:

When the Input tree is:

And the given value of k is: 3

Output

In the recursive revere in-order traversal approach to the problem - find the $k^{th}$ largest element in bst, we are traversing the input binary search tree only once using the in-order traversal of the binary search tree. We are not using any extra space.

Time Complexity

Since we are traversing the input binary search tree only once, the time complexity of the recursive revere in-order traversal approach to the problem - find the kth largest element in bst comes out to be O(n), where n is the size of the input binary search tree.

Space Complexity

Since we are not using any extra space, the space complexity of the recursive revere in-order traversal approach to the problem - find the $k^{th}$ largest element in bst comes out to be O(1).

Approach 3: Iterative Approach - Reverse In-Order Traversal using Stack

So far we have seen two approaches that were based on recursion as we were using recursive in-order traversal approaches. Is there any way to solve the provided problem without using recursion? The answer is yes.

Another efficient algorithm for the problem - of finding the $k^{th}$ largest element in bst is to iteratively traverse the binary search tree in reverse order and store the values into a stack data structure (similar to what we have performed above in the reverse in-order traversal approach).

Approach 4: By using Reverse Morris Traversal

Before getting into the reverse morris traversal approach, let us first get a brief introduction to the Morris Traversal.

Morris traversal is a tree traversal algorithm (it can be in-order, pre-order, or post-order) that does not use any stack or recursion for the tree traversal.

Another efficient algorithm for the problem - find the kth largest element in bst is to perform the reverse Morris Traversal. So, we would traverse the tree in reverse order and decrement the value of k in each iteration. Once the value of k reaches 0, we have found our kth largest element in bst.

We can also use a counter that will increment in each traversal. Once the value of the counter is the same as k then we have found our answer.

Algorithm

The pseudo-code for the above-discussed algorithm can be:

1. Initialize two pointers.
2. The first pointer (currentNode) will point to the root node.
3. The second pointer (KthLargestNode) will point to NULL.
4. Perform the below steps until the currentNode does not becomes NULL.
   • If the currentNode has no right child, increment the counter.
   • Check whether the value of counter is the same as k or not.
     • If it is the same then return the currentNode's data as the kth largest element in bst.
     • Else, make the currentNode point to its left subtree.
   • If the currentNode has the right child, then make the currentNode point to its right subtree.
   • Now we need to move the left child of the currentNode, so we can use another pointer that will help us to traverse the leftmost child of the currentNode.
     • Move to the left-most child of the currentNode and let it be pointed by another pointer namely successor.
     • Now check if the successor has no left child.
       • If the successor has no left child then make the successor.left point to the currentNode and move the currentNode to its right child.
       • Else, increment the counter by 1.
       • Again check whether the value of counter is the same as k or not.
       • If it is the same then return the currentNode's data as the kth largest element in bst.
       • Else, make the currentNode point to its left subtree.

Code Implementation

Let us code the above-discussed algorithm for better understanding.

C++ code:

Java code:

Python code:

When the Input tree is:

And the given value of k is: 3

Output

In the reverse morris traversal approach to the problem - find the kth largest element in bst, we are traversing the input binary search tree only once using the reverse morris traversal algorithm of the binary search tree. We are not using any extra space apart from a few pointers.

Time Complexity

Since we are traversing the input binary search tree only once, the time complexity of the reverse morris traversal approach to the problem - find the $k^{th}$ largest element in bst comes out to be O(n), where n is the size of the input binary search tree.

Space Complexity

Since we are not using any extra space, the space complexity of the reverse morris traversal approach to the problem - find the $k^{th}$ largest element in bst comes out to be O(1).

Approach 5: Efficient Approach - using Augmented BST

Before getting into the augment tree approach, let us first get a brief introduction to the Augmented Binary Search Trees.

An augment binary search tree is a special kind of bst which stores the data in sorted manner apart from that, it also keeps the track of some kind of information about the element based on which the elements of the bst have been stored.

So, another efficient algorithm for the problem - find the kth largest element in bst is to use the idea behind the augmented BSTs. The idea is very simple, we can keep track of the number of nodes present in the left subtree and the right subtree during the insertion of the node in the bst. As we need to find the kth largest element, we need to keep track of the elements present in the right subtree of the current node.