Kth Smallest Element in a BST — Medium Coding Interview Question

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) among all node values in the tree.

Example

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

Output: 1

Constraints

• The number of nodes is in the range [1, 10⁴]
• 1 ≤ k ≤ number of nodes

Topics & Companies

Topics: trees, binary-search

Asked by: Amazon, Meta, Microsoft, Bloomberg

Optimal Solution Complexity

Time complexity: O(h + k). Space complexity: O(h).

Practice more

• All DSA Problems
• DSA Patterns