Trees · 113Medium
Kth Smallest Element in a BST
Given the root of a binary search tree and an integer k, return the kth smallest value in the tree (1-indexed).
Constraints
- The tree holds n nodes, 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4
- INPUT FORMAT
- `root` is a TreeNode object, not an array. The arrays in EXAMPLES are the level-order
- serialization the platforms print — breadth-first, with `null` for a missing child. The
- test runner builds a real tree from that array before calling your function.
Examples
kthSmallest([3, 1, 4, null, 2], k = 1) -> 1 kthSmallest([5, 3, 6, 2, 4, null, null, 1], k = 3) -> 3 kthSmallest([1], k = 1) -> 1 kthSmallest([3, 1, 4, null, 2], k = 4) -> 4 // k = n gives the maximum kthSmallest([2, 1, 3], k = 2) -> 2 // perfectly balanced BST kthSmallest([1, null, 2, null, 3], k = 3) -> 3 // right-skewed BST
Edge cases
- k is 1-indexed, so k = 1 is the minimum.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — collect all values and sort them, discarding the BST property.
- Target
- O(h + k) time — an in-order traversal (iterative with a stack) that counts nodes and returns the moment the counter hits k.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/07-trees/113-kth-smallest-element-in-a-bst.js ./practice c 113