230. Kth Smallest Element in a BST
Model: qwen3.5:9b
Topics: Binary Search,Tree
FAANG asked: 1
Acceptance rate: 62.9%
Problem Breakdown
We are given the root of a Binary Search Tree (BST) and an integer k. Our goal is to find the value of the node that represents the kth smallest element in the tree. The input guarantees 1 <= k <= n, where n is the total number of nodes, so we don’t need to handle invalid k values like 0 or greater than n.
Key constraints and properties:
- BST Property: For any node, all left descendants are smaller, and all right descendants are larger. This implies an in-order traversal (Left -> Root -> Right) visits nodes in strictly ascending order of their values.
- Input Format: Standard LeetCode
TreeNodestructure (val,left,right). - Edge Cases to Consider: A tree with only one node, a skewed tree (worst-case height), and finding the minimum or maximum element (k=1 vs k=n).
Intuition
A brute-force approach would be to perform an in-order traversal of the entire tree, store all values in a list, sort them if necessary (though BST guarantees order naturally), and then pick the k-1 index. This takes O(N) time but requires O(N) extra space for storage before we even find the answer.
However, since it’s a BST, we don’t need to store all elements or wait until the end of traversal. We can stop exactly when we reach our target count. The core insight is that in-order traversal yields sorted values. Therefore, if we maintain a counter during an in-order walk and increment it every time we visit a node’s value (specifically after visiting its left subtree), the moment this counter equals k, we have found our answer.
Follow-up Optimization: If updates are frequent, maintaining simple BST structure isn’t enough because finding the kth element would require traversing O(N) in worst case per query. To optimize for frequent insert/delete and queries, one might use an Order Statistic Tree. This involves augmenting each node with a size field representing the number of nodes in its left subtree (including itself). With this augmentation:
- We can calculate how many elements are smaller than current root by looking at
left.size. - If
k <= left.size, go left; ifk == left.size + 1, we found it; otherwise, subtract from k and go right. This allows O(log N) query time without full traversal.
Approach
I will implement an iterative in-order traversal using a stack. I prefer this over recursion for two reasons:
- It avoids Python’s default recursion limit issues (which would crash on deep/skewed trees with ).
- It gives explicit control to stop immediately once
kis found, preventing unnecessary traversal of the rest of the tree if we find a match early in the sorted sequence.
The algorithm proceeds as follows:
- Initialize an empty stack and push all left children starting from root until null (this simulates going down the “left spine”).
- Pop nodes one by one, incrementing our counter
counteach time we process a node’s value. - If
count == k, return the current node’s value immediately. - After processing a node, push its right child onto the stack and repeat step 1 (push left children of that new branch).
Complexity Analysis
- Time Complexity: O(H), where H is the height of the tree. In the worst case (skewed BST like a linked list), H = N, so it’s O(N). In a balanced BST, H = log N. Since we stop early upon finding
k, this is generally faster than traversing all nodes unlesskis nearn. - Space Complexity: O(H) for the stack used in iterative traversal to store path from root to current node.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kthSmallest(root: 'TreeNode', k: int) -> int:
stack = []
current = root
# Iterative in-order traversal to find the k-th smallest element
while True:
if current is not None:
# Go as far left as possible, pushing nodes onto stack
stack.append(current)
current = current.left
elif len(stack) > 0:
# Pop node from stack (this simulates returning up the tree)
current = stack.pop()
# Increment count and check if we found our target
k -= 1
if k == 0:
return current.val
# Move to right subtree after processing left side of this node
current = current.right
else:
break
return -1 # Should not reach here given constraints (k <= n)
Edge Cases Handled
- Single Node Tree: The loop pushes root, pops it immediately.
kdecrements to 0 on first pop ifk=1, returning the node’s value correctly. - Skewed BST (Linked List): Iterative approach handles deep trees without hitting recursion depth limits (
RecursionError). - Finding Minimum Element: If
k=1, we traverse all left children, then process root immediately after popping stack, decrementingkto 0 and returning. This is the most efficient path for minimum value (O(H)). - Empty Tree Constraints: The problem constraints state , so an empty tree or invalid
kare not possible inputs per specification; however, if they were, a check at start would be added before entering loop.