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

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:

```
[10]
/ \
[5] [15]
/ \ / \
[1] [7] [11] [18]
```

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.

- Create an array
`sortedNodeValues`

that will store the inorder traversal of the given Binary Search Tree. - 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. - 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.

- 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`

.

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.

- 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. - To reverse Inorder traverse an array, we simply traverse it as
`right -> root -> left`

. Thisi way, the highest value gets traversed first. - 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. - Traverse the right subtree by passing
`tree.right`

in the`reverseInorder()`

function. - 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. - Return lastVisitedNode at the end.

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