Kth Smallest Element in a BST

Leetcode problem 230; Difficulty: Medium

Problem Statement

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Constraints:

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

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

Follow up:

If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize? (To be implemented)

Submitted Solution

The implemented solution recevied the following rating on Leetcode: