DSA

Kth Smallest Element in a BST

Covers: Brute Force, Better, Optimal. Optimal — Time O(n), Space O(1).

August 8, 2026
DSABinary Search TreeBSTLeetCodePracticeHeapPriority Queue

practice here

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.

Brute Force#

Collect all node values using any traversal order, sort the resulting list, and return the element at index k-1. This ignores the BST's sorted structure entirely, so sorting costs O(n log n) on top of the O(n) traversal.

  • Find any traversal of BST
  • Sort the stored traversal
  • return k-1 element

Time Complexity: O(nlogn)

Space Complexity: O(n)

Better Approach#

The BST property guarantees that an inorder traversal (left → root → right) visits all nodes in strictly ascending order. So we can collect all values via inorder traversal into a vector — no sorting needed — and simply return the element at index k-1. This drops the time from O(n log n) to O(n), though we still use O(n) extra space for the vector.

cpp
/**
 * 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:
    void inOrderTraversal(TreeNode* root, vector<int> &inorder)
    {
        if(!root)
            return;

        inOrderTraversal(root->left, inorder);
        inorder.push_back(root->val);
        inOrderTraversal(root->right, inorder);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> inorder;
        inOrderTraversal(root, inorder);
        return inorder[k-1];
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Optimal Approach#

We don't need to store all values — just count nodes as we visit them in inorder order and stop the moment the counter reaches k. Pass a counter and answer variable by reference through the recursion; increment the counter on each node visit, and record the value when the counter equals k, then avoid any further recursion. This keeps time at O(n) in the worst case (the k-th smallest could be the last node) but reduces extra space from O(n) to O(1) by eliminating the storage vector.

cpp
/**
 * 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:
    void inOrderTraversal(TreeNode* root, int &cnt, int &ans, int k)
    {
        if(!root)
            return;

        inOrderTraversal(root->left, cnt, ans, k);
        cnt++;
        if(cnt==k){
            ans = root->val;
            return;
        }
        inOrderTraversal(root->right, cnt, ans, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        int cnt=0;
        int ans;
        inOrderTraversal(root, cnt, ans, k);
        return ans;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Related articles

DSATask SchedulerThree approaches — Math formula O(n), Greedy Max-Heap O(n log k), Sorted Array O(n). Find minimum CPU intervals with cooldown constraint.DSASort Characters By FrequencyMax-heap on character frequency. Time O(n + d log d), Space O(d) where d = distinct characters.DSAK Closest Points to OriginMax-heap of size k — evict the farthest point on each insert. Time O(n log k), Space O(k).