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) {
        auto node = traverse(root, k);
        return node->val;
    }

private:
    TreeNode *traverse(TreeNode *root, int &k) {
        if (root != nullptr) {
            TreeNode *left = traverse(root->left, k);
            if (left != nullptr) {
                return left;
            }

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

            return traverse(root->right, k);
        }

        return nullptr;
    }
};