DSA · Trees · #96

Kth Smallest Element in a BST

Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given the `root` of a binary search tree (BST) and an integer `k`, return the **kth smallest** value (1-indexed) among all node values in the tree. A BST has the property that for every node, all values in its left subtree are smaller and all values in its right subtree are larger. Implement `kthSmallest(root, k)`, where each node is `{ val, left, right }` and `k` is guaranteed to be between 1 and the number of nodes.

Examples

root = [3,1,4,null,2], k = 1 → 1 — Inorder order is 1,2,3,4. The 1st smallest is 1.
root = [5,3,6,2,4,null,null,1], k = 3 → 3 — Inorder order is 1,2,3,4,5,6. The 3rd smallest is 3.
root = [1], k = 1 → 1

Constraints

· The number of nodes n is in the range [1, 10^4].
· 1 <= k <= n
· 0 <= Node.val <= 10^4
· The tree is a valid binary search tree.

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.