algoadvance

Leetcode 230. Kth Smallest Element in a BST

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the kth smallest value (1-indexed) of all the values in the BST.

Clarifying Questions

  1. What are the constraints on k?
    • 1 <= k <= number of nodes in the BST.
  2. Can the tree contain duplicate values?
    • No, the problem assumes all values in the BST are unique.
  3. What is the size range of the BST?
    • Typically, constraints are not given explicitly, but we will assume a range up to several thousand nodes for practical purposes.
  4. Is the given BST guaranteed to be valid?
    • Yes, the input is assumed to be a valid binary search tree.

Strategy

To find the kth smallest element in a BST, an in-order traversal is an effective method. This traversal visits nodes in ascending order for a BST. During the traversal, we simply count the nodes until we reach the kth node.

The steps are:

  1. Perform an in-order traversal.
  2. Keep track of the count of nodes visited.
  3. When the count equals k, record the value of the current node.

Code

Here is a C++ implementation of the solution:

#include <iostream>
using namespace std;

// 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 = -1;
        inorderTraversal(root, k, count, result);
        return result;
    }

private:
    void inorderTraversal(TreeNode* node, int k, int &count, int &result) {
        if (!node) return;

        inorderTraversal(node->left, k, count, result);

        count++;
        if (count == k) {
            result = node->val;
            return;
        }

        inorderTraversal(node->right, k, count, result);
    }
};

Time Complexity

The time complexity is O(N), where N is the number of nodes in the BST. This is because in the worst case, we might need to traverse all nodes if k is the largest possible (k == N).

The space complexity is O(H), where H is the height of the BST. This space is required for the call stack during the recursion. For a balanced BST, the height H = log(N). In the worst case (unbalanced BST), H can be up to N.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI