LeetCode #230 Medium

Kth Smallest Element in BST

Return the k-th smallest value in a BST.

bstinorderdfs

02

Intuition

Inorder traversal of a BST emits values in sorted order — so the k-th visited node is the answer. Traverse iteratively and stop early; no need to materialize the whole list.

How to spot this pattern

In-order traversal of a BST emits values in sorted order — that single fact turns "k-th smallest" into "stop after k emissions". Doing it with an explicit stack rather than recursion is what lets you stop early instead of walking the whole tree, which matters when k is small or the follow-up asks about frequent queries.

03

Approach

1

Inorder = sorted stream

Left, node, right yields ascending values by the BST property.

2

Iterate with an explicit stack

Push the left spine; pop = next smallest; then walk the popped node's right subtree's left spine.

3

Stop at k

Decrement k per pop; return when it hits zero — O(h + k) work.

04

Solution & live demo

▶1class Solution:
▶2    def kthSmallest(self, root, k):
▶3        stack = []
▶4        node = root
▶5        while True:
▶6            while node:
▶7                stack.append(node)
▶8                node = node.left
▶9            node = stack.pop()
▶10            k -= 1
▶11            if k == 0: return node.val
▶12            node = node.right

05

Common pitfalls

Collecting the full in-order list first

✗ Wrong

vals = []
def dfs(n):
    if not n: return
    dfs(n.left); vals.append(n.val); dfs(n.right)
dfs(root)
return vals[k - 1]

✓ Right

while True:
    while node: stack.append(node); node = node.left
    node = stack.pop()
    k -= 1
    if k == 0: return node.val
    node = node.right

Correct, but it visits all n nodes and allocates all n values to answer a question that's settled after k. The iterative form stops the instant the count runs out — O(h + k) instead of O(n).

Decrementing k before popping

✗ Wrong

while node:
    stack.append(node)
    k -= 1
    node = node.left

✓ Right

node = stack.pop()
k -= 1
if k == 0: return node.val

Pushing is not visiting — nodes go onto the stack in descending order down the left spine, long before their turn. A node is only visited in sorted position when it comes off the stack.

Going left again after popping

✗ Wrong

node = stack.pop()
node = node.left

✓ Right

node = stack.pop()
...
node = node.right

The left subtree was already fully consumed on the way down — that's why this node is next in order. Revisiting it loops forever; the unexplored part is the right subtree.

06

Edge cases

k = tree size

Traversal ends exactly on the maximum node.

Frequent queries with inserts

Augment nodes with subtree sizes → O(h) per query (LeetCode's follow-up).

07

Complexity

Time

O(h + k)

Space

O(h)

Early-stopping iterative inorder.