Skip to main content

Kth largest element in BST

Problem​

Given a Binary search tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    vector<int> v;

    void traversal(Node* root) {
        if (!root) return;
        traversal(root->right);
        v.push_back(root->data);
        traversal(root->left);
    }

    int kthLargest(Node* root, int K) {
        traversal(root);
        return v[K - 1];
    }
};