230. Kth Smallest Element in a BST

2023, Apr 09 One min read

1. Description

Given the root of a binary search tree, and an integer k, return the $k^{th}$ smallest value (1-indexed) of all the values of the nodes in the tree.

2. Example

Example 1

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

Example 2

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

3. Constraints

The number of nodes in the tree is n.
1 <= k <= n <= $10^4$
0 <= Node.val <= $10^4$

4. Solutions

Binary Search Tree

n is the number of nodes in root
Time complexity: O(logn + k)
Space complexity: O(logn)

class Solution {
public:
    int kthSmallest(TreeNode *root, int k) {
        int target = 0;
        find_kth_smallest_value(root, k, target);
        return target;
    }

private:
    void find_kth_smallest_value(TreeNode *root, int &k, int &target) {
        if (root == nullptr || k == 0) {
            return;
        }

        find_kth_smallest_value(root->left, k, target);
        if (k == 0) {
            return;
        }

        --k;
        if (k == 0) {
            target = root->val;
        } else {
            find_kth_smallest_value(root->right, k, target);
        }
    }
};