## Introduction

This blog will discuss the various approaches to find out **Kth Largest Element in Binary Search Tree**. Before jumping into the problem, let’s first understand what exactly a Binary Search Tree is?

A Binary Search Tree is a type of tree data structures where for each and every node, all the nodes in the tree which are on the left of this node which means the left subtree of that node is lesser value than the current value of that node and all the nodes in the tree which are on the right of this node which means the right subtree of that node has a value greater than the value of current node, along with the fact that both left subtree and right subtree are Binary Search Trees.

Let’s say this BST has n nodes. We have to find out Kth Largest element in this BST, where K is always less equal to n.

**Recommended:** Try the Problem yourself before moving on to the solution.

## Brute Force Approach

Binary search trees have a property that If we do Inorder traversal of the binary search tree, then we get sorted data. We will use this property to solve this given problem. First, we will do an inorder traversal of BST, and we will keep on storing the traversed elements in the list, and afterward, we will go to the Kth location of that list and return that element’s value.

### Algorithm

**Step 1**. Create a recursive function that will accept the root of the tree and a list of integers.

**Step 2**. The recursive function makes a call to the left subtree

**Step 3**. Add the current node’s value to the list.

**Step 4**. The recursive function makes a call to the right subtree

**Step 5**. Return from the recursive function.

**Step 6**. Go back to the caller function and return the Kth value from the list.

```
import java.util.ArrayList;
import java.util.List;
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val)
{
this.val = val;
}
}
public class BST {
public void KthLargestElement(TreeNode root, List<Integer> list)
{
if(root == null)
{
return;
}
// Traverse left subtree
KthLargestElement(root.left, list);
list.add(root.val);
// Traverse right subtree
KthLargestElement(root.right, list);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(5);
root.left = new TreeNode(2);
root.right = new TreeNode(9);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(8);
root.right.right = new TreeNode(12);
int k = 2;
BST obj = new BST();
List<Integer> list = new ArrayList<Integer>();
obj.KthLargestElement(root, list);
// As list is sorted, so index from beginning will size - ‘K’
int index = list.size() - k ;
int KthLargestElement = list.get(index);
System.out.println(KthLargestElement);
}
}
```

**Algorithm Complexity of Kth Largest Element: **

**Time Complexity: **O(N)

The time complexity of inorder traversal of BST is O(N), as we will be traversing over each node for the inorder traversal.

**Space Complexity: **O(N)

As we are maintaining a sorted list of ‘N’ nodes, hence space complexity will be O(N).