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
- An in-order traversal of a BST visits the values in ascending order.
- So the answer is simply the
k-th node visited. - The iterative in-order traversal can stop as soon as
kreaches 0, which avoids traversing the whole tree. - 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.rightafter 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.
🧩 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 # 转向右子树