Untitled

import java.util.*;

class Node {
    int data;
    Node left, right;

    public Node(int value) {
        data = value;
        left = right = null;
    }
}

public class Main {
    
    // Function to insert a new node in BST
    public static Node insert(Node root, int data) {
        if (root == null) {
            return new Node(data);
        }
        if (data < root.data) {
            root.left = insert(root.left, data);
        } else {
            root.right = insert(root.right, data);
        }
        return root;
    }

    // Utility function to find the Kth largest element
    private static void KthLargestUtil(Node root, int k, int[] count, int[] result) 
    {
        if (root == null || count[0] >= k) {
            return;
        }

        // Reverse Inorder Traversal (Right -> Root -> Left)
        KthLargestUtil(root.right, k, count, result);
        
        count[0]++;
        if (count[0] == k) {
            result[0] = root.data;
            return;
        }
        
        KthLargestUtil(root.left, k, count, result);
    }

    // Function to find the Kth largest element
    public static int KthLargest(Node root, int k) {
        int[] count = {0};  // Counter for visited nodes
        int[] result = {-1}; // Store the Kth largest element
        KthLargestUtil(root, k, count, result);
        return result[0];
    }

    // Main function
    public static void main(String[] args) {
        Node root = new Node(4);
        root = insert(root, 2);
        root = insert(root, 9);
        root = insert(root, 5);
        root = insert(root, 12);
        root = insert(root, 1);

        int k = 2;
        int result = KthLargest(root, k);
        System.out.println("The " + k + "th largest property price is: " + result);
    }
}