MediumNeetCode150TreeDepth-First SearchBinary Search TreeBinary Tree
Kth Smallest Element in a BST
Return kth smallest value in BST.
Examples
Input
root = [3,1,4,null,2], k = 1
Output
1
1st smallest is 1.
Constraints
- •
1 <= k <= n <= 10^4 - •
0 <= Node.val <= 10^4
Approaches
Store sorted values.
CodeT: O(n) | S: O(n)
def kthSmallest(root, k):
r=[]
def io(n):
if not n: return
io(n.left); r.append(n.val); io(n.right)
io(root); return r[k-1]Stop after k elements.
CodeT: O(n) | S: O(h)
def kthSmallest(root, k):
st=[]; c=root
while st or c:
while c: st.append(c); c=c.left
c=st.pop(); k-=1
if k==0: return c.val
c=c.rightCount and stop at k.
CodeT: O(n) | S: O(h)
def kthSmallest(root, k):
self.cnt=0; self.res=0
def io(n):
if not n: return
io(n.left)
self.cnt+=1
if self.cnt==k: self.res=n.val; return
io(n.right)
io(root); return self.resComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Inorder Store All | O(n) | O(n) | Store sorted values. |
| Inorder Iterative | O(n) | O(h) | Stop after k elements. |
| Early Termination | O(n) | O(h) | Count and stop at k. |
Inorder Store All
T: O(n)S: O(n)
Store sorted values.
Inorder Iterative
T: O(n)S: O(h)
Stop after k elements.
Early Termination
T: O(n)S: O(h)
Count and stop at k.
Common Mistakes
Traversing entire tree unnecessarily
Not using BST property
Off-by-one with k