LeetCode · #230

Kth Smallest Element in a BST Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #230

🏗️

Pattern

BST — inorder = sorted order

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

Example

 Input: root = [3,1,4,null,2], k = 1
Output: 1 // Inorder: [1,2,3,4] → 1st smallest = 1 

Constraints

• 1 ≤ k ≤ n ≤ 10⁴ • 0 ≤ Node.val ≤ 10⁴

Section Two · Approach 1

Full Inorder + Index — O(n)

Do a full inorder traversal, collect all values into a sorted list, return the k-1 index. Works but always traverses all n nodes even if k=1.

Section Three · Approach 2

Early-Stop Inorder — O(H + k)

Inorder traversal of a BST visits nodes in ascending order. Count as you go — when you've visited k nodes, the current node is the answer. Stop early.

💡 Mental model: BST inorder = sorted list. Instead of building the whole list, just walk through it counting: "1st... 2nd... 3rd... kth! — stop and return."

🎯 Iterative is preferred:

The iterative stack-based inorder lets you stop as soon as you hit k, without unwinding recursion.
O(H) to reach the leftmost node + O(k) to count to k.

Section Four · Trace

Visual Walkthrough

BST [3,1,4,null,2], k=1

Section Five · Implementation

Code — Java & Python

Java — Iterative Inorder

 import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
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; // found kth!
curr = curr.right;
        }
return -1; // unreachable
}
}

Python — Iterative Inorder

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Full inorder	O(n)	O(n)
Early-stop inorder	O(H + k)	O(H)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k=1	Any BST	Leftmost node. Stop immediately after first pop.
k=n	Any BST	Rightmost node. Full traversal needed.
Skewed left	`3→2→1`	Stack depth = n. All nodes pushed before first pop.

⚠ Common Mistake: Using 0-indexed counting. The problem says 1-indexed — the 1st smallest is the minimum, not the 0th. Decrement k before checking k == 0, or check count == k after incrementing.

← Back to BST problems

LearningTree

LC 230 · Kth Smallest Element in a BST — Solution & Explanation | DSA Guide