Algorithm-Day45-Kth-Smallest-Element-in-a-BST-lc-230

Posted on In , Views:

🧩 Problem Description

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

💬 Example

1
2
Input: root = [3,1,4,null,2], k = 1
Output: 1
1
2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

💡 Approach 1: Inorder Traversal (Iterative)

A BST’s inorder traversal produces nodes in sorted order.
We can simply traverse in-order and stop when we reach the k-th node.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (--k == 0) return curr.val;
            curr = curr.right;
        }
        return -1; // should not reach here if k is valid
    }
}

💡 Approach 2: Recursive Inorder Traversal

We can also use recursion with a counter to track when we reach the k-th element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private int count = 0;
    private int result = 0;

    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);
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(h + k) — h is tree height; in the worst case O(n) if tree is unbalanced.
  • Space Complexity: O(h) for stack/recursion.

✍️ Summary

  • Inorder traversal is perfect for BST because it gives sorted order.
  • For large trees with many queries, consider augmenting each node with subtree size to get O(log n) queries.
  • Related problems:
    • lc-98 — Validate BST
    • lc-701 — Insert into BST
    • lc-450 — Delete Node in BST