Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Brute Force Approach 
2.1.
Algorithm 
3.
Better Approach
3.1.
Algorithm 
4.
Optimal Approach 
4.1.
Algorithm 
5.
Frequently Asked Questions
5.1.
What is a Binary Search Tree?
5.2.
What is a Threaded Binary Tree?
5.3.
What is Morris Traversal?
6.
Conclusion
Last Updated: Mar 27, 2024

Kth Largest Element BST

Author Harsh Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

Binary Tree

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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Better Approach

We are using the auxiliary space ‘N’ in the above approach to maintain the list. Let's try to solve the problem without using a list. From the above approach we can deduce that (N - K)th element would be our answer where ‘N’ is the total number of nodes and ‘K’ is the user input. Let’s find out the size of the tree and then maintain a variable that keeps track of how many elements have been traversed. Once we reach the (N - K)th element, we will return that element, and our work is done.

Algorithm 

Step 1. Create a utility function to find out the size of the tree.

Step 2. Define an instance level variable ‘currentCount’ and initialize it to -1. 

Step 3. Create a recursive function that will take the root node and size of the tree and ‘K’ index.

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

Step 5. Increase ‘currentCount’.

Step 6. Check if currentCount == size - K, then return that node.

Step 7. Call the recursive function for the right subtree.



class TreeNode{
int val;
TreeNode left;
TreeNode right;

TreeNode(int val)
{
this.val = val;
}
}

 
public class BST {

// We are considering first element as 0th index element so we have initialized it to -1
int currentCount = -1;

 
// Utility function to get tree size
public int getTreeSize(TreeNode root)
{
if(root == null)
             {
return 0;
}

 
return getTreeSize(root.left) + getTreeSize(root.right) + 1;
}

public TreeNode KthLargestElement(TreeNode root, int n, int k)
{
if(root == null)
             {
return null;
}

 
// Traverse left tree
TreeNode left = KthLargestElement(root.left, n, k);

if(left != null)
             {
return left;
             }

currentCount++;

if(currentCount == n - k)
             {
return root;
             }

// Traverse right tree
TreeNode right = KthLargestElement(root.right, n, k);

if(right != null)
             {
return right;
             }

return null;
       
}

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();
    
    int n = obj.getTreeSize(root);
    
    TreeNode KthLargestNode = obj.KthLargestElement(root, n, k);
    
    System.out.println(KthLargestNode.val);
    
}

 
}

 

Algorithm Complexity of Kth Largest Element: 

Time Complexity: O(N)

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

 

Space Complexity: O(H)

We are not using any extra space, but recursion is internally using ‘H’ (Height) space, so complexity is O(H)

Optimal Approach 

A threaded Binary Tree needs to be used to solve this problem efficiently. Let’s understand what Threaded Binary Trees are? 

In a Threaded Binary Tree, the nodes will store the in-order predecessor/successor rather than NULL in the left/right child pointers.

So the basic idea of a threaded binary tree is that for the nodes whose right pointer is null, we store the node’s in-order successor (if-exists), and for the nodes whose left pointer is null, we store the in-order predecessor of the node(if-exists).

Note that a tree’s leftmost and the rightmost child pointer always points to null, as their in-order predecessor and successor do not exist. 

You can visit this link for more understanding of Threaded Binary Trees.

Another concept needed to solve this problem is Reverse Morris Traversal, which is the reverse of Morris Traversal.

The idea of Morris's traversal is based on the Threaded Binary Tree.  This traversal will create links to the predecessor back to the current node to trace it back to the top of a binary tree. Here we don’t need to find a predecessor for every node, and we will be seeing a predecessor of nodes with only a valid left child.

You can visit this link for more understanding of Tree Traversals.

While doing Reverse Morris Traversal, we will keep track of the count, and once that count is equal to ‘K’, we will return that element. 

Algorithm 

Step 1. Initialize a counter variable to 0.

Step 2. Run a while loop until the root is not null.

Step 3. If the root has no right child, then increase the counter and check if the counter is equal to K. If yes, we found our desired element and now move to the left subtree of that root.

Step 4 Else, there are 2 scenarios possible -

a) Find the inorder successor of the root. If inorder successor’s left child == null

      then set root as the left child of its inorder 

         Successor and move the root node to its right.

b) Else if root node, and it's inorder successor already has threaded link -

      1) Set the left pointer of the inorder successor as NULL.

      2) Increase counter and check if counter == K, then return that element.

      3) Else go to the left child.




class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val)
	{
	this.val = val;
	}
}

 
public class BST {

// Traverse from Right to the left in inorder fashion and use Morris Traversal on it
public TreeNode KthLargestElement(TreeNode root, int k)
{

 
int counter = 0;
TreeNode KthLargestElement = null;
 
    while (root != null)
    {
        if (root.right == null)
        {
         // Keep increasing counter with each visiting nodes
            counter++;
            if (k == counter)
                KthLargestElement = root;
 
            root = root.left;
        }
        else
        {
         TreeNode successor = root.right;
 
         // This will help to find inorder successor of the current node
            while(successor.left != null && successor.left != root)
            {
                successor = successor.left;
          	}
 
            if (successor.left == null)
            {
             successor.left = root;
             root = root.right;
            }
            else 
            {
                   // This block will help to restore the original links of tree
                   successor.left = null;
            
                   // Keep increasing counter with each visiting nodes
                   counter++;
                  if (k == counter)
                  {
                      KthLargestElement = root;
                  } 
                  root = root.left;
            }
        }
    }
    return KthLargestElement;
       
}

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 = 3;
    
    BST obj = new BST();
         
    TreeNode KthLargestNode = obj.KthLargestElement(root, k);
    
    System.out.println(KthLargestNode.val);
    
}

 
}

 

Algorithm Complexity of Kth Largest Element: 

Time Complexity: O(N)

We are traversing the tree in inorder fashion  and modifying the links between the leaf nodes at the same time, which will be done in constant time so total time complexity is O(N) + O(1) = O(N)

Space Complexity: O(1)

We are using constant extra space, so space complexity is O(1).
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is a Binary Search Tree?

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

What is a Threaded Binary Tree?

In a Threaded Binary Tree, the value of nodes will store the in-order predecessor/successor instead of NULL in the left or right or both child pointers. So, in threaded binary tree nodes whose right pointer is null, we store the node’s in-order successor (if-exists), and for the nodes whose left pointer is null, we store the in-order predecessor of the node(if-exists).

Note that a tree’s leftmost and the rightmost child pointer always points to null, as their in-order predecessor and successor do not exist. 

What is Morris Traversal?

The idea of Morris's traversal is based on the Threaded Binary Tree. This traversal will create links to the predecessor back to the current node to trace it back to the top of a binary tree. Here we don’t need to find a predecessor for every node, and we will be finding a predecessor of nodes with only a valid left child.

Conclusion

This article discussed the various approaches to finding out Kth Largest Element in Binary Search Tree. We explored the concept of Morris’s traversal and found out how we can use this algorithm to solve problems in constant space. Try this problem on Coding Ninjas Studio and you and learn more about this in C++ DSA course.

If you think that this blog helped you, then share it with your friends!

Recommended Reading:

Until then, All the best for your future endeavors, and Keep Coding.

 

Previous article
Find the Median of BST in O(N) Time and O(1) Space
Next article
Number of pairs with a given sum in a Binary Search Tree
Live masterclass