💬 Discord
Sign In
NeetCode #443LC-230MediumTreesBlind 75NC 150NC 250
← Back to All Problems

#443 · #230 · Kth Smallest Element in a BST(二叉搜索树中第 K 小的元素)

📌 Problem Statement & Constraints

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed). Constraints: the number of nodes is in [1, 10^4], 1 <= k <= n. The follow-up asks for an optimal solution for frequent lookups.

💡 Core Algorithmic Approaches

  1. An in-order traversal of a BST visits the values in ascending order.
  2. So the answer is simply the k-th node visited.
  3. The iterative in-order traversal can stop as soon as k reaches 0, which avoids traversing the whole tree.
  4. The follow-up (frequent queries) is answered by augmenting each node with a subtree size, giving O(h) per query.

💻 Benchmark Python3 Implementation

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        st = []
        cur = root
        while True:
            while cur:                     # descend to the leftmost node
                st.append(cur)
                cur = cur.left
            cur = st.pop()                 # visit
            k -= 1
            if k == 0:
                return cur.val             # stop early
            cur = cur.right                # then the right subtree

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(h + k): the descent to the leftmost node is O(h), then k visits.
💾 Space Complexity
O(h) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Traversing the whole tree and indexing: O(n) when only k nodes need visiting.
  • Forgetting cur = cur.right after visiting: the traversal would loop on the same node.
  • Using 0-indexed k: the problem is 1-indexed, so the decrement happens before the check.
  • Assuming the tree is balanced: h can be n for a degenerate BST, so the worst case is O(n).