52. Kth Smallest Element in a BST · DSA Practice

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

Example 1

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

Output: 1

Example 2

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

Output: 3

Hint 1

In-order traversal of a BST visits values in sorted order.

Hint 2

Stop as soon as you have visited k nodes.

TreeBST

Approach 1: Collect in-order

Store all values, return index k−1.

⏱ Time O(n)💾 Space O(n)

Approach 2: Iterative in-order, early stop ✅

Stop after k pops.

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

Reference solution for Iterative in-order, early stop (time O(h + k), space O(h)). Each solution passes every test in all four languages.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack, node = [], root
        while True:                      # iterative in-order: values come out sorted
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.val
            node = node.right

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (true) {                   // iterative in-order
            while (node != null) { stack.push(node); node = node.left; }
            node = stack.pop();
            if (--k == 0) return node.val;
            node = node.right;
        }
    }
}

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<TreeNode*> st;
        TreeNode* node = root;
        while (true) {                   // iterative in-order
            while (node) { st.push_back(node); node = node->left; }
            node = st.back(); st.pop_back();
            if (--k == 0) return node->val;
            node = node->right;
        }
    }
};

function kthSmallest(root, k) {
  const stack = [];
  let node = root;
  while (true) { // iterative in-order
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop();
    if (--k === 0) return node.val;
    node = node.right;
  }
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Binary Trees & BSTs.