Kth Smallest Element in a BST
Medium · Trees · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree, counting from 1: k = 1 asks for the minimum and k = n for the maximum.
In a binary search tree every value in a node’s left subtree is smaller than the node, and every value in its right subtree is larger. So reading the tree in order — left subtree, node, right subtree — lists the values sorted. The k-th value of that walk is the answer, and the walk can stop right there.
Values are distinct. Trees here are at most 500 levels deep, so a recursive solution is safe.
The node type and two helpers are provided:
Examples
Input: root = [3,1,4,None,2], k = 1 Output: 1
In order the values are 1, 2, 3, 4, and the first of them is 1.
Input: root = [5,3,6,2,4,None,None,1], k = 3 Output: 3
In order the values are 1, 2, 3, 4, 5, 6. The third is 3.
Constraints
- 1 <= k <= n <= 10^4, where n is the number of nodes
- 0 <= Node.val <= 10^4, and the values are distinct
- the tree is a valid binary search tree
- the tree is at most 500 levels deep (LeetCode allows a 10^4-node chain; tightened so recursion fits in the browser)
Approaches
- Collect every value and sort — time O(n log n), space O(n)
Follow-up
Suppose the BST is modified frequently (inserts and deletes) and you need the k-th smallest value often. How would you change your approach?
Related problems
Start free on Cariara · Coding problems · System design studio
