Kth Smallest element in a BST

Link: LeetCode - Kth Smallest Element in a BST

Problem Statement

Given the root of a binary search tree and an integer k, return the kth smallest element in the BST.

Examples

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⁴
0 <= Node.val <= 10⁴

Intuition

In a Binary Search Tree, an inorder traversal yields the elements in sorted order.

So, the kth smallest element is the kth node visited during an inorder traversal.

Approach: Inorder Traversal (Recursive)

Perform an inorder traversal.
Keep a counter of how many elements have been seen.
When count == k, record and return the current node’s value.

Java Code

class Solution {
    private int count = 0;
    private int result = -1;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;

        inorder(node.left, k);

        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        inorder(node.right, k);
    }
}

Alternate Approach: Iterative Inorder with Stack

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();

        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            k--;

            if (k == 0) return root.val;

            root = root.right;
        }
    }
}

Time & Space Complexity

Time Complexity: O(H + k)
- Worst-case H = height of the tree (log N for balanced, N for skewed)
- Traverses up to k nodes in the worst case.
Space Complexity: O(H)
- Due to recursion or stack space.

Dry Run

Tree:

k = 3

Inorder traversal: 1 → 2 → 3 → 4 → 5 → 6

After visiting 1 → count = 1
After visiting 2 → count = 2
After visiting 3 → count = 3 → return 3

Conclusion

This problem demonstrates how the inorder traversal of a BST can directly help in selecting order-based queries like finding the kth smallest or kth largest elements.