Practice/Meta/Leetcode 230. Kth Smallest Element in a BST

Leetcode 230. Kth Smallest Element in a BST

CodingMust

Problem

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) among all node values in the tree.

A binary search tree satisfies the property that for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are greater than the node's value.

Requirements

1. Find and return the kth smallest element where k is 1-indexed
2. Handle trees with varying shapes (balanced, skewed, etc.)
3. Utilize the BST property to optimize your solution
4. You may assume k is always valid (1 ≤ k ≤ total number of nodes)

Constraints

• The number of nodes in the tree is n where 1 <= n <= 10^4
• 1 <= k <= n
• 0 <= Node.val <= 10^4
• The tree is guaranteed to be a valid binary search tree

Examples

Example 1:

Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1 Explanation: The smallest value in the tree is 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Explanation: Values in ascending order are [1,2,3,4,5,6]. The 3rd smallest is 3

Example 3:

Input: root = [2,1,3], k = 2 Output: 2 Explanation: In sorted order [1,2,3], the 2nd element is 2