Binary Search Trees: Kth Largest Element in a BST

Problem Statement:

You are given BST and a kth element in the given tree.

Then you need to give the kth largest element.

Solution

Here we need to do reverse inorder traversal of BST and we need to keep a count of nodes visited.

It means, in reverse in-order traversal visit the right node then center then left node recursively.

Then keep the count of nodes visited so far and then when the count becomes equal to k, stop the traversal and print the node value.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 


void kth_largest_helper(Node *root, int k, int &c)
{

    if (root == NULL || c >= k)
        return;
  
    kth_largest_helper(root->right, k, c);
  
    c++;
  
    if (c == k)
    {
        cout << "K'th largest element is "
             << root->data << endl;
        return;
    }
  
    kth_largest_helper(root->left, k, c);
}
  
void get_kth_largest(Node *root, int k)
{
    int c = 0;
  
    kth_largest_helper(root, k, c);
}
  

int main()
{
    Node *root_1 = NULL; 
    root_1 = insert_into_bst(root_1, 1); 
    insert_into_bst(root_1, 2); 
    insert_into_bst(root_1, 3); 
    insert_into_bst(root_1, 4); 
    insert_into_bst(root_1, 5); 

    get_kth_largest(root_1, 2);

    return 0;
}

Output:

K'th largest element is 4