Kth Largest Element in a BST

Given a binary search tree (BST) and an integer k, write a program to find the k-th largest element in the BST. The 1st largest element is the largest element in the tree, the 2nd largest is the second largest, and so on.

Input/Output Examples

plaintext
Example 1:
Input:

       8
      / \
     4   12
    / \  / \
   2   6 10 14

k = 2
Output: 12
Explanation: The 2nd largest element in the BST is 12.

Example 2:
Input:

       8
      / \
     4   12
    / \  / \
   2   6 10 14

k = 5
Output: 6
Explanation: The 5th largest element in the BST is 6.

Approach to Find the K-th Largest Element in a BST

  1. Reverse Inorder Traversal:
    • In a BST, an inorder traversal visits the nodes in increasing order. By performing a reverse inorder traversal (right → root → left), we can visit the nodes in decreasing order.
    • As we traverse the tree, we keep a counter to count how many nodes we have visited. When the counter reaches k, we have found the k-th largest element.
  2. Recursive Approach:
    • Start from the root and traverse the tree using a reverse inorder traversal.
    • Each time we visit a node, we decrement the value of k. When k reaches 0, we have found the k-th largest element.
  3. Edge Case:
    • If the tree is empty or k is larger than the number of nodes in the tree, return an error or -1.

C++ Program to Find the K-th Largest Element in a BST

cpp
#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Helper function to find the k-th largest element
void findKthLargestUtil(TreeNode* root, int& k, int& result) {
    if (root == NULL || k == 0) {
        return;
    }

    // Traverse the right subtree first (reverse inorder)
    findKthLargestUtil(root->right, k, result);

    // Decrement k and check if we've found the k-th largest element
    k--;
    if (k == 0) {
        result = root->data;
        return;
    }

    // Traverse the left subtree
    findKthLargestUtil(root->left, k, result);
}

// Function to find the k-th largest element in a BST
int findKthLargest(TreeNode* root, int k) {
    int result = -1;
    findKthLargestUtil(root, k, result);
    return result;
}

int main() {
    // Create a sample BST
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(4);
    root->right = new TreeNode(12);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(6);
    root->right->left = new TreeNode(10);
    root->right->right = new TreeNode(14);

    int k = 2;
    int kthLargest = findKthLargest(root, k);

    if (kthLargest != -1) {
        cout << "The " << k << "-th largest element is: " << kthLargest << endl;
    } else {
        cout << "Invalid input or k is larger than the number of nodes." << endl;
    }

    return 0;
}

Java Program to Find the K-th Largest Element in a BST

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class KthLargestInBST {

    // Helper function to find the k-th largest element
    public static void findKthLargestUtil(TreeNode root, int[] k, int[] result) {
        if (root == null || k[0] == 0) {
            return;
        }

        // Traverse the right subtree first (reverse inorder)
        findKthLargestUtil(root.right, k, result);

        // Decrement k and check if we've found the k-th largest element
        k[0]--;
        if (k[0] == 0) {
            result[0] = root.data;
            return;
        }

        // Traverse the left subtree
        findKthLargestUtil(root.left, k, result);
    }

    // Function to find the k-th largest element in a BST
    public static int findKthLargest(TreeNode root, int k) {
        int[] result = new int[] {-1};  // Store the result
        int[] kArr = new int[] {k};     // Use an array to modify k
        findKthLargestUtil(root, kArr, result);
        return result[0];
    }

    public static void main(String[] args) {
        // Create a sample BST
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(4);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(6);
        root.right.left = new TreeNode(10);
        root.right.right = new TreeNode(14);

        int k = 2;
        int kthLargest = findKthLargest(root, k);

        if (kthLargest != -1) {
            System.out.println("The " + k + "-th largest element is: " + kthLargest);
        } else {
            System.out.println("Invalid input or k is larger than the number of nodes.");
        }
    }
}

Python Program to Find the K-th Largest Element in a BST

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Helper function to find the k-th largest element
def find_kth_largest_util(root, k, result):
    if root is None or k[0] == 0:
        return

    # Traverse the right subtree first (reverse inorder)
    find_kth_largest_util(root.right, k, result)

    # Decrement k and check if we've found the k-th largest element
    k[0] -= 1
    if k[0] == 0:
        result[0] = root.data
        return

    # Traverse the left subtree
    find_kth_largest_util(root.left, k, result)

# Function to find the k-th largest element in a BST
def find_kth_largest(root, k):
    result = [-1]  # Store the result
    k_arr = [k]    # Use a list to modify k
    find_kth_largest_util(root, k_arr, result)
    return result[0]

# Example usage
if __name__ == "__main__":
    # Create a sample BST
    root = TreeNode(8)
    root.left = TreeNode(4)
    root.right = TreeNode(12)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(6)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(14)

    k = 2
    kth_largest = find_kth_largest(root, k)

    if kth_largest != -1:
        print(f"The {k}-th largest element is: {kth_largest}")
    else:
        print("Invalid input or k is larger than the number of nodes.")
  • Time Complexity: O(h + k), where h is the height of the BST and k is the number of nodes we need to visit to find the k-th largest element. In the worst case, this could be O(n) for a skewed tree, but for a balanced BST, it is O(log n + k).
  • Space Complexity: O(h), where h is the height of the tree due to the recursive call stack.

DSA

6936

206

Related Articles