medium

Kth Smallest Element in a BST

Given the root of a binary search tree and an integer k, return the k-th smallest value stored in the tree (1-indexed).

Constraints

1 ≤ n ≤ 10^4
1 ≤ k ≤ n
0 ≤ node value ≤ 10^4

Examples

in: root = [3,1,4,null,2], k = 1

out: 1

in: root = [5,3,6,2,4,null,null,1], k = 3

out: 3

Recognition clues

A BST — in-order traversal yields values in sorted order
Only the k-th element is needed, so stop early
Iterative traversal with an explicit stack

Pattern

Tree Traversal

Nearly every tree problem is a traversal with the right information passed down (bounds, depth) or returned up (height, best path through this node). Inorder on a BST yields sorted order, which solves kth-smallest and validation; BFS with a queue yields levels.

Binary Search Tree Binary Tree Stack

Solution

Perform an in-order traversal, which visits BST nodes in ascending order. Use an explicit stack: push the whole left spine, pop a node, decrement k, and when k reaches zero return that node's value; otherwise move to its right child and repeat. Stopping at the k-th visit avoids traversing the entire tree.

time O(h + k)space O(h)

Alternative approaches

Store subtree sizes in each node to answer in O(h) per query when the tree is queried repeatedly or modified. Collecting the full in-order list is O(n) space.

Code it yourself

Solve in

Hints:

Learn Binary Tree ▶ Visualize