Kth Smallest Element in a BST
Medium
Tree
Depth-First Search
Binary Search Tree
Binary Tree
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
Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Example 3
Input: root = [1], k = 1
Output: 1

Constraints

  • •The number of nodes in the tree is in the range [1, 10⁴].
  • •0 <= Node.val <= 10⁴
  • •1 <= k <= number of nodes in the tree
Time Complexity
O(h+k)
Space Complexity
O(h)
14
Case 1
Input: [3,1,4,null,2] 1
Expected: 1
Case 2
Input: [5,3,6,2,4,null,null,1] 3
Expected: 3
Case 3
Input: [1] 1
Expected: 1