Kth Smallest / Largest in BST

Problem Statement

Find the Kth smallest or largest element in a BST.

Example: Input: [3,1,4,null,2], k=2 → Output: 2

Approach 1: Inorder Traversal

Explanation: Inorder gives sorted elements. Return kth element.

Time Complexity: O(n)

Space Complexity: O(h)

count = 0
result = NULL
function inorder(node, k):
    if node == NULL: return
    inorder(node.left, k)
    count += 1
    if count == k: result = node.val
    inorder(node.right, k)

Approach 2: Reverse Inorder for Largest

Explanation: Traverse right->node->left to get descending order.

Time Complexity: O(n)

Space Complexity: O(h)

count = 0
function reverseInorder(node, k):
    if node == NULL: return
    reverseInorder(node.right, k)
    count += 1
    if count == k: result = node.val
    reverseInorder(node.left, k)