MediumTrees

Kth Smallest Element in a BST

Q: Example 1: What is the output for input root = [3,1,4,null,2], k = 1?

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

Q: Example 2: What is the output for input root = [5,3,6,2,4,null,null,1], k = 3?

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

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)

Practice this problem with an AI interviewer

TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.

Start a free interview