BST - Kth Largest

#include <bits/stdc++.h> // Includes common standard libraries (iostream, etc.)
#include "BST.h"         // Assumed to contain Node class, insertIntoBST, takeinput, levelOrderTraversal

using namespace std;     // Use the standard namespace

// Note: The Node class, insertIntoBST, takeinput, and levelOrderTraversal
// are assumed to be defined in "BST.h".
/*
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) { ... }
};

Node* insertIntoBST(Node* root, int data) { ... }
void takeinput(Node* &root) { ... }
void levelOrderTraversal(Node* root) { ... }
*/

// Function to find the Kth largest element in a BST using a reverse in-order traversal.
// 'index' is passed by reference to maintain a global count across recursive calls.
// Time Complexity: O(H + K) in average case, O(N) in worst case.
// Space Complexity: O(H) for recursion stack.
int kthLargest(Node* root, int &index, int K) {
    // Base Case: If the current node is NULL, we can't find Kth largest here.
    if(root == NULL) {
        return -1; // Return -1 to indicate "not found yet" or an error.
    }

    // 1. Recursively traverse the RIGHT subtree first (to get largest elements).
    int rightResult = kthLargest(root->right, index, K);

    // If the Kth largest was found in the right subtree, propagate the result up immediately.
    if(rightResult != -1) {
        return rightResult;
    }

    // 2. Process the current node (root).
    // Increment the counter as we've visited another node in reverse in-order sequence.
    index++;
    // If the current node is the Kth node in reverse in-order sequence, it's our answer.
    if(index == K) {
        return root->data; // Found the Kth largest element!
    }

    // 3. Recursively traverse the LEFT subtree.
    // If not found in right or current node, it must be in the left part.
    return kthLargest(root->left, index, K);
}

int main() {
    Node* root = NULL; // Initialize root of the BST
    int K, ans;        // K for the target rank, ans for the result

    cout << "Enter data to create BST : ";
    takeinput(root); // Build the BST

    cout << "Enter the value of K (e.g., 1 for largest, 2 for second largest): ";
    cin >> K; // Get the value of K from the user

    cout << endl << "Level Order Traversal of the created BST : " << endl;
    levelOrderTraversal(root); // Print the tree structure (optional, for verification)

    int index = 0; // Initialize the counter for reverse in-order traversal to 0
    ans = kthLargest(root, index, K); // Call the function to find the Kth largest

    // Print the result
    if (ans != -1) {
        cout << endl << "The " << K << "th largest element is = " << ans << endl;
    } else {
        cout << endl << "Could not find the " << K << "th largest element (K might be too large or tree empty)." << endl;
    }

    return 0;
}

/*
Example INPUT for tree creation:
50 20 70 10 30 60 80 -1

Expected Tree Structure:
        50
       /  \
      20  70
     / \  / \
    10 30 60 80

Reverse In-order traversal (descending sequence): 80, 70, 60, 50, 30, 20, 10

Example Scenarios:
1. Enter the value of K : 1
   Output: The 1th largest element is = 80

2. Enter the value of K : 4
   Output: The 4th largest element is = 50

3. Enter the value of K : 7
   Output: The 7th largest element is = 10

4. Enter the value of K : 8 (K is larger than total nodes)
   Output: Could not find the 8th largest element (K might be too large or tree empty).
*/

1. Binary Search Tree (BST) Recap

• A Binary Search Tree (BST) has the property where for any node:
  • All values in its left subtree are less than its own data.
  • All values in its right subtree are greater than its own data.
• Key Insight: While an In-order traversal gives elements in ascending order, a Reverse In-order traversal (visiting Right child, then Root, then Left child) will visit nodes in descending order. This is the core principle for finding the Kth largest element efficiently.

2. Supporting Components (Briefly)

• Node class: Defines the structure of a BST node (data, left, right).
• insertIntoBST, takeinput, levelOrderTraversal: These functions (assumed to be in BST.h) are used to create and display the BST.

3. kthLargest(Node* root, int &index, int K) Function (Recursive Reverse In-order Traversal)

• Purpose: To find the Kth largest integer value in the Binary Search Tree.

• Core Idea: Perform a Reverse In-order traversal (Right -> Root -> Left). As we visit nodes in decreasing order, we maintain a counter (index). When this counter reaches K, the current node’s data is the Kth largest.

• Parameters:

  • Node* root: The current node being processed in the traversal.
  • int &index: A reference to an integer counter. This is crucial as it allows the index to be updated globally across all recursive calls, tracking the order of visited nodes.
  • int K: The target position (1-indexed) of the largest element we are looking for.

• Logic Flow (Reverse In-order Traversal with Counter):

  1. Base Case:
     • if (root == NULL): If we’ve traversed past a leaf or the tree is empty, return -1 (or some other indicator for “not found yet”).
  2. Traverse Right:
     • int rightResult = kthLargest(root->right, index, K);
     • Recursively call kthLargest on the right subtree first. The largest elements are found on the right side of the tree.
     • if (rightResult != -1): If the Kth largest element was found within the right subtree (indicated by rightResult not being -1), immediately return that rightResult up the call stack, as we’ve found our answer.
  3. Process Current Node (Root):
     • index++;: If the Kth element wasn’t found in the right subtree, increment the index counter for the current root node. This node is the next largest in sequence.
     • if (index == K): If the index now matches K, this root->data is the Kth largest element. Return root->data.
  4. Traverse Left:
     • return kthLargest(root->left, index, K);
     • If the Kth element was not found in the right subtree and the current root wasn’t the Kth, then it must be in the left subtree. Recursively call kthLargest on the left subtree.

4. Complexity Analysis

• Time Complexity: O(H + K) in the average case for a balanced tree, effectively O(K) if K is small. In the worst case (skewed tree or K is close to N), it’s O(N).
  • The algorithm performs a reverse in-order traversal, visiting nodes in decreasing order. It stops once the Kth element is found.
• Space Complexity: O(H)
  • Due to the recursion call stack, where H is the height of the tree.
  • Worst Case (Skewed Tree): H = N, leading to O(N) space.
  • Best Case (Balanced Tree): H = log N, leading to O(log N) space.

---