⚡Flashcard Drill➔
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).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems

中文速览与面试要点

二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root,和一个整数 k,请你设计一个算法查找其中第 k 个 最小 元素(从 1 开始计数)。约束:树中的节点数为 n;1 ≤ k ≤ n ≤ 10^4;0 ≤ Node.val ≤ 10^4。

核心要点

  • 中序遍历 + 提前返回(标准解) :BST 的中序遍历是升序的,因此遍历到第 k 个节点即为答案。
  • 迭代中序(推荐) :用栈模拟中序遍历,每弹出一个节点就让 k 减一,k 归零时立即返回,无需遍历完整棵树。
  • 为什么用迭代而非递归 :递归无法在中途「提前返回」并保留结果(除非用全局变量或异常),迭代可以立即 return。
  • 复杂度 :O(h + k) 时间(先下行到最左,再访问 k 个节点),O(h) 空间。

常见陷阱

  • 把整棵树中序遍历成数组再取第 k 个 :O(n) 时间、O(n) 空间,未利用「可提前返回」的优势。
  • 递归中序但无法提前返回 :递归会遍历完整棵树(除非用异常或全局标志)。
  • k 从 0 开始计数 :题目明确从 1 开始。
  • 忘记 cur = cur.right :会导致死循环。

参考实现

class Solution:
    def kthSmallest(self, root: 'TreeNode', k: int) -> int:
        stack = []
        cur = root
        while True:
            while cur:                  # 一路向左
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()           # 访问节点(中序)
            k -= 1
            if k == 0:
                return cur.val
            cur = cur.right             # 转向右子树