Kth Smallest Element in a BST

Kth Smallest Element in a BST

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.

Examples

Example 1:

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

    3
   / \
  1   4
   \
    2

Example 2:

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

        5
       / \
      3   6
     / \
    2   4
   /
  1

Explanation: The sorted order is [1, 2, 3, 4, 5, 6], and the 3rd smallest is 3.

Constraints

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

Expected Complexity

• Time: O(H + k) where H is the height of the tree
• Space: O(H)