# Kth Largest in a BST

Find Kth largest in a BST - Given a BST and a number k, find the kth largest element in the BST.

## Basic Solution - Inorder traversal

As we know, the inorder traversal of a given Binary Search Tree always the elements sorted in increasing order.

For Example, Consider the below tree:

``````        
/    \
     
/   \    /   \
       
``````

The `inorder` traversal of this tree will be `[1, 5, 7, 10, 11, 15, 18]`. This is because Inorder traversal follows `left -> root -> right` traversal property.

1. Create an array `sortedNodeValues` that will store the inorder traversal of the given Binary Search Tree.
2. The `inorder` method will first traverse the left subtree, then add the root value in the `sortedNodeValues` array and finally will traverse the right subtree.
3. Now since the `sortedNodeValues` array contains the sorted values, we can simply print `sortedNodeValues[sortedNodeValues.length - k]` values to get the 3rd largest from the end. This will be our solution.

### Complexity Analysis

• Time: `O(n)` Since we will be visiting the all the nodes atleast once.
• Space: `O(n)` Since this can be a skewed tree of height `n`.

## Reverse Inorder Approach

Here, we are going to take a different approach. Instead of traversing the array completely and then taking the value from the end of the array, we are going to traverse the array in `descending order`. As and when we reach the value that we need, (let's say third largest) - we stop and return the value.

1. We declare a class `TreeInfo` that has `lastVisitedNode` and `numberOfVisitedNodes` variables. These are required because we need to compare these against the `kth` value which is given by the problem.
2. To reverse Inorder traverse an array, we simply traverse it as `right -> root -> left`. Thisi way, the highest value gets traversed first.
3. While traversing, we check if `numberOfVisitedNodes >= k`. If this is the case, we simply return the `lastVisitedNode` because that will be the answer. This will be the base case.
4. Traverse the right subtree by passing `tree.right` in the `reverseInorder()` function.
5. If the `numberOfVisitedNodes` of TreeInfo class is less than `k`, Increment the count, Mark the last visited as the current node and finally traverse the right subtree.
6. Return lastVisitedNode at the end.
Solve Kth Largest in a BST on Algochurn

## Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn