Kth Smallest Element in a BST

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

A binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node's key.
• The right subtree of every node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees are also binary search trees.

Approach

Perform an in-order traversal (left, node, right), which visits nodes in ascending order for a BST. Use an explicit stack to traverse iteratively and decrement k each time a node is visited. When k reaches zero, that node is the answer.

Why It Works

In-order traversal of a BST yields values in sorted order. Therefore, the k-th visited node is exactly the k-th smallest element. The iterative traversal preserves this order while using only stack space.

Complexity

• Time: O(h + k)
• Space: O(h)

Reference Implementation (Python)

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            k -= 1
            if k == 0:
                return cur.val
            cur = cur.right
        return 0