Kth Smallest Element 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Given a BST, find the kth smallest element (1-indexed).

#       3
#      / \
#     1   4
#      \
#       2
# Inorder: [1, 2, 3, 4]
# k=1 → 1 (smallest)
# k=3 → 3

Since inorder traversal of BST = sorted order, the kth smallest is just the kth element in inorder traversal!

Approach 1: Full inorder → return result[k-1]. Simple but O(n) space.
Approach 2: Iterative inorder with early stopping — stop after visiting k nodes. O(k) time.
Use a stack for iterative inorder: go as far left as possible, visit, then go right

The iterative approach with early stopping is more efficient when k is small.

📋 Instructions

Implement `kth_smallest(root, k)` using iterative inorder traversal. Test with k=1 and k=3.

Use a stack. Push all left children. Pop = visit (decrement k). If k == 0, return that value. Then go to right child and push its left children. Repeat.

🧪 Test Cases

Input

kth_smallest(root, 1)

Expected

1

Test case 1

Input

kth_smallest(root, 3)

Expected

3

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›