Kth Smallest Element in a BST

You get the root of a binary search tree (BST) and a number k. Return the k-th smallest value in the tree.

Counting starts at 1, so k = 1 means the smallest value.

In a BST, every value in a node's left subtree is smaller than the node. Every value in its right subtree is larger.

The trees below are listed level by level, top to bottom and left to right. A missing child is written as nil.

Example 1:

      6
     / \
    2   9
   / \   \
  1   4   11

Input: root = [6,2,9,1,4,nil,11], k = 4
Output: 6
Explanation: Sorted, the values are:
1, 2, 4, 6, 9, 11.
The 4th one is 6.

Example 2:

      10
     /
    5
   / \
 -2   7

Input: root = [10,5,nil,-2,7], k = 1
Output: -2
Explanation: k = 1 asks for the smallest value.
That is -2, the leftmost node.

Example 3:

 -3
   \
    0
     \
      8

Input: root = [-3,nil,0,nil,8], k = 3
Output: 8
Explanation: The tree has 3 nodes.
So the 3rd smallest value is the largest one, 8.

Constraints:

• The tree has n nodes, from 1 to 15.
• All values are different.
• Each value is from -100 to 100.
• k is from 1 to n.