All problems
MediumTrees

Kth Smallest Element in a BST

amazonmetagoogleuberbloombergoracle

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

Example 1:

    3
   / \
  1   4
   \
    2

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

Example 2:

        5
       / \
      3   6
     / \
    2   4
   /
  1

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

Examples

Example 1

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

Output: 1

Explanation: The sorted values in the BST are [1, 2, 3, 4]. The 1st smallest element is 1.

Example 2

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

Output: 3

Explanation: The sorted values in the BST are [1, 2, 3, 4, 5, 6]. The 3rd smallest element is 3.

Constraints

  • -The number of nodes in the tree is n.
  • -1 <= k <= n <= 10^4
  • -0 <= Node.val <= 10^4

Optimal Complexity

Time

O(H + k)

Space

O(H)

One problem, two ways to prep

Choose between solo practice and interview simulation

Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.

Try 5-Minute Audio InterviewAI Interview Mode