Kth Smallest Element in a BST medium

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the k^th smallest element in the BST.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Steps and Explanation

The key to efficiently solving this problem lies in leveraging the properties of a Binary Search Tree (BST). In a BST, the left subtree contains only nodes with values smaller than the current node, and the right subtree contains only nodes with values larger. We can use an inorder traversal to visit the nodes in ascending order. The k^th smallest element will be the k^th node visited during this inorder traversal.

We'll use a recursive inorder traversal approach with a counter to track the k^th element.

1. Recursive Inorder Traversal: We recursively traverse the BST. The order is: left subtree, root, right subtree.

2. Counter: We maintain a count variable. Every time we visit a node, we increment the counter.

3. Kth Smallest Check: When the count reaches k, we've found the k^th smallest element, so we return the node's value.

4. Base Case: If we reach a null node (end of a branch) or the count exceeds k, we stop the recursion and return.

Code (C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = 0;
        int result = 0;  // Initialize to store the result

        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (node == nullptr || count >= k) return; //Base Case

            inorder(node->left);
            count++;
            if (count == k) {
                result = node->val;  //Store the value when count == k
                return;
            }
            inorder(node->right);
        };

        inorder(root);
        return result;
    }
};

Complexity Analysis

• Time Complexity: O(H + k), where H is the height of the BST. In the worst case (a skewed BST), H can be N (number of nodes), resulting in O(N) time. However, in a balanced BST, H is log(N), making the time complexity closer to O(k) which is better if k is small. The inorder traversal visits at most k nodes.

• Space Complexity: O(H) in the worst case due to the recursive call stack. In a balanced BST, this becomes O(log N), and in a skewed BST, it can be O(N). We also use constant extra space for variables.