Back to solutions

Kth Smallest Element in a BST

MediumBST

Return the k-th smallest value in a binary search tree (1-indexed).

Open problem
Constraints
  • 1 <= k <= nodes <= 10^4
  • 0 <= Node.val <= 10^4

In-order traversal counts up

Time O(h + k)Space O(h)

An in-order walk of a BST visits values in sorted order. Use an iterative stack and stop at the k-th popped node.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        if (--k == 0) return cur->val;
        cur = cur->right;
    }
    return -1;
}