Kth Smallest Element in a BST

Problem

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.

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

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

Follow up: If the BST is modified often and you need to find the kth smallest frequently, how would you optimize?

Solution

Approach: Inorder Traversal

The key insight is that inorder traversal of a BST produces values in sorted order. We can count while traversing and return the kth element.

Implementation

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.count = 0
        self.result = None

        def inorder(node):
            if not node or self.result is not None:
                return

            # Traverse left
            inorder(node.left)

            # Process current node
            self.count += 1
            if self.count == k:
                self.result = node.val
                return

            # Traverse right
            inorder(node.right)

        inorder(root)
        return self.result

Iterative Version:

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        current = root
        count = 0

        while current or stack:
            # Go to leftmost node
            while current:
                stack.append(current)
                current = current.left

            # Process node
            current = stack.pop()
            count += 1
            if count == k:
                return current.val

            # Move to right subtree
            current = current.right

Complexity Analysis

Time Complexity: O(h + k), where h is the height of the tree. We go down to the leftmost node (h), then visit k nodes.
Space Complexity: O(h) for recursion stack or explicit stack.

Key Insights

Inorder = Sorted: Inorder traversal of a BST visits nodes in ascending order by value.
Early Termination: We can stop as soon as we find the kth element, no need to traverse the entire tree.
1-Indexed: The problem uses 1-indexed counting (k=1 means smallest, not k=0).
Follow-up Optimization: For frequent queries, we could augment each node with the size of its subtree, allowing O(h) queries.
Stack vs Recursion: Both approaches work equally well. Iterative might be preferred for very deep trees to avoid stack overflow.