BST - Kth smallest

#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 smallest element in a BST using an in-order traversal approach.
// 'index' is passed by reference to maintain a global count across recursive calls.
// Time Complexity: O(H + K) or O(N) in worst case (skewed tree or K close to N)
// Space Complexity: O(H) for recursion stack
int kthSmallest(Node* root, int &index, int K) {
    // Base Case: If the current node is NULL, we can't find Kth smallest here.
    if(root == NULL) {
        return -1; // Return -1 to indicate "not found yet"
    }

    // 1. Recursively traverse the left subtree.
    // The Kth smallest might be in the left part.
    int leftResult = kthSmallest(root->left, index, K);

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

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

    // 3. Recursively traverse the right subtree.
    // If not found in left or current node, it must be in the right part.
    return kthSmallest(root->right, 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 smallest, 2 for second smallest): ";
    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 in-order traversal to 0
    ans = kthSmallest(root, index, K); // Call the function to find the Kth smallest

    // Print the result
    if (ans != -1) {
        cout << endl << "The " << K << "th smallest element is = " << ans << endl;
    } else {
        cout << endl << "Could not find the " << K << "th smallest 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

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

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

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

3. Enter the value of K : 7
   Output: The 7th smallest element is = 80

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

1. Binary Search Tree (BST) Recap

• A Binary Search Tree (BST) maintains the property that 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: An In-order traversal of a BST visits nodes in ascending (sorted) order. This property is fundamental to finding the Kth smallest 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. kthSmallest(Node* root, int &index, int K) Function (Recursive In-order Traversal)

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

• Core Idea: Since an In-order traversal naturally produces elements in sorted order, we can perform an In-order traversal and simply keep a counter (index). When this counter reaches K, the current node’s data is our answer.

• Parameters:

  • Node* root: The current node being processed in the traversal.
  • int &index: A reference to an integer counter. This is crucial because index needs to be shared and updated across all recursive calls to keep a global count of visited nodes.
  • int K: The target position (1-indexed) of the smallest element we are looking for.

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

  1. Base Case:
     • if (root == NULL): If we’ve traversed past a leaf node (or the tree is empty), there’s no node here. Return -1 to indicate that the element hasn’t been found yet in this path.
  2. Traverse Left:
     • int leftResult = kthSmallest(root->left, index, K);
     • Recursively call kthSmallest on the left subtree. This ensures that smaller elements are processed first.
     • if (leftResult != -1): If the Kth smallest element was found within the left subtree (indicated by leftResult not being -1), immediately return that leftResult 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 left subtree, increment the index counter for the current root node.
     • if (index == K): If the index now matches K, this root->data is the Kth smallest element. Return root->data.
  4. Traverse Right:
     • return kthSmallest(root->right, index, K);
     • If the Kth element was not found in the left subtree and the current root wasn’t the Kth, then it must be in the right subtree. Recursively call kthSmallest on the right subtree.

• Initial Call in main:

  • int index = 0;: Initialize the counter to 0 before the first call.
  • ans = kthSmallest(root, index, K);: Start the traversal.

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 an in-order traversal, which visits nodes in increasing 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.

---