k-th Smallest in BST

Given a BST and an integer k, the task is to find the kth smallest element in the BST. If there is no kth smallest element present then return -1.

Examples:

Input: root = [2, 1, 3], k = 2
 
Output: 2
Explanation: 2 is the 2nd smallest element in the BST.

Input: root = [2, 1, 3], k = 5
 
Output: -1
Explanation: There is no 5th smallest element in the BST as the size of BST is 3.

Input: root = [20, 8, 22, 4, 12, N, N, N, N, 10, 14], k = 3

Output: 10
Explanation: 10 is the 3rd smallest element in the BST.

Constraints:

• 1 <= number of nodes, k <= 10⁵
  
• 1 <= node->data <= 10⁵

Approach 01:

class Solution {
  public:
    int kthSmallestValue = -1;

    void findKthSmallest(Node* root, int &k) {
        if (root == nullptr)
            return;

        findKthSmallest(root->left, k);
        k--;

        if (k == 0) {
            kthSmallestValue = root->data;
            return;
        }

        findKthSmallest(root->right, k);
    }

    // Return the Kth smallest element in the given BST
    int kthSmallest(Node* root, int k) {
        findKthSmallest(root, k);
        return kthSmallestValue;
    }
};

class Solution:
    def __init__(self):
        self.kthSmallestValue = -1

    def findKthSmallest(self, root, k):
        if not root:
            return

        self.findKthSmallest(root.left, k)
        k[0] -= 1

        if k[0] == 0:
            self.kthSmallestValue = root.data
            return

        self.findKthSmallest(root.right, k)

    # Return the Kth smallest element in the given BST
    def kthSmallest(self, root, k):
        k = [k]  # Use a list to pass by reference
        self.findKthSmallest(root, k)
        return self.kthSmallestValue

Time Complexity:

• Inorder Traversal:

  Since we perform an inorder traversal of the BST, visiting each node once, the traversal takes \( O(N) \) in the worst case.

• Early Stopping:

  In the best case, the traversal stops as soon as the kth smallest element is found, making the time complexity \( O(k) \).

• Overall Time Complexity:

  Worst case: \( O(N) \), Best case: \( O(k) \).

Space Complexity:

• Recursive Stack:

  In the worst case, the recursion depth reaches \( O(N) \) for a skewed BST, leading to \( O(N) \) space.

• Balanced BST Case:

  For a balanced BST, the recursion depth is \( O(\log N) \), making the space complexity \( O(\log N) \).

• Overall Space Complexity:

  Worst case: \( O(N) \), Best case: \( O(\log N) \).