Kth Smallest Element in a BST

Problem Overview
The "Kth Smallest Element in a BST" problem involves finding the kth smallest value (1-indexed) in a binary search tree (BST), leveraging its sorted in-order traversal property. This is a classic Oracle interview question tagged with Tree, DFS, BST, and Binary Tree, commonly appearing on platforms like LeetCode (problem 230).[1][5]

Full Problem Statement

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.

• You may assume k is always valid (1 ≤ k ≤ number of nodes in BST).
• The solution typically uses in-order DFS traversal since BST in-order visits nodes in ascending order.[5][1]

Input/Output Examples

Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: In-order traversal yields; 1st smallest is 1.[2][3][4][1]

Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: In-order:; 3rd smallest is 3.[3][4][6][1][2][5]

Example 3 (from GeeksforGeeks variant):
Tree: 12 / \ 8 22 / \ / 4 12 10 14, k = 3
Output: 8
Explanation: In-order yields smaller values leading to 8 as 3rd.[3]

Constraints

• Number of nodes: 1 ≤ n ≤ 10^4
• Node values: -10^4 ≤ Node.val ≤ 10^4
• 1 ≤ k ≤ n (k always valid)
  These ensure O(h + k) time is efficient, where h is tree height (worst-case O(n) for skewed trees).[1][5]