Kth Smallest Element in a BST (LeetCode 230): Inorder Traversal and Beyond
3 views
Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed). It is a short problem, but it tests whether you really use the BST property, and the follow-up question is where strong candidates stand out.
The key property
An inorder traversal (left, node, right) of a BST visits values in sorted order. So the kth node visited in inorder is the answer. Say this first; it is the entire insight.
Approach 1: Recursive inorder with early stop
def kth_smallest(root, k):
count = 0
answer = None
def inorder(node):
nonlocal count, answer
if not node or answer is not None:
return
inorder(node.left)
count += 1
if count == k:
answer = node.val
return
inorder(node.right)
inorder(root)
return answer
Stopping early matters: you visit only about h + k nodes instead of the whole tree.
Approach 2: Iterative with a stack
def kth_smallest_iter(root, k):
stack, node = [], root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
Time is O(h + k), space O(h), where h is the tree height. Interviewers often prefer this version because it avoids recursion limits on skewed trees and makes the early exit obvious.
A naive answer to avoid
Collecting every value into a list and sorting it works, but ignores the BST property and costs O(n log n). Mention it only as a baseline.
The classic follow-up
"What if the tree is modified often (inserts and deletes) and you need kth smallest frequently?" The strong answer is to augment each node with the size of its subtree. Then:
- If the size of the left subtree is k - 1, the current node is the answer.
- If it is at least k, go left.
- Otherwise, go right with k reduced by left size + 1.
Each query becomes O(h), and inserts and deletes update sizes along the path. In a balanced tree, that is O(log n) for everything. This is the idea behind order-statistic trees.
Edge cases
- k equals 1 (the leftmost node) or k equals the number of nodes (the rightmost).
- A completely skewed tree, where h equals n.
- Duplicates, if allowed, depend on how the BST places equal values; ask the interviewer.
How to present it
State the inorder property, write the iterative version, trace a small tree with k = 3, then volunteer the subtree-size augmentation for the follow-up. If you blank on the stack loop under pressure, Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, quietly reminding you of the pattern while you explain your reasoning in your own words.