Skip to main content

Kth Smallest Element in a BST

Problem​

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

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    void helper(TreeNode* root, vector<int>& v) {
        if (!root) return;
        helper(root->left, v);
        v.push_back(root->val);
        helper(root->right, v);
    }

   public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL) return 0;
        vector<int> v;
        helper(root, v);
        return v[k - 1];
    }
};