Kth Smallest Number in a Binary Search Tree

Given the root of a Binary Search Tree and an integer k, return the k-th smallest value among all node values in the tree (1 indexed, so k = 1 returns the smallest value).

Example 1

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

      3
     / \
    1   4
     \
      2

Output: 1.

Example 2

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

          5
         / \
        3   6
       / \
      2   4
     /
    1

Output: 3.

Constraints

• The number of nodes is in the range [1, 10^4].
• 0 <= Node.val <= 10^4.
• 1 <= k <= (number of nodes in the tree).
• Follow-up: if the BST is modified often (insert/delete calls) and you need to find the kth smallest repeatedly, how would you optimize?