230. Kth Smallest Element in a BST

Quick Identifier

Topic: trees
Pattern: Inorder traversal on BST
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 230

Quick Sights

Time Complexity: O(h + k) from the optimal approach.
Space Complexity: O(h) from the optimal approach.
Core Mechanism: Given the root of a BST and an integer k, return the kth smallest value (1-indexed) in the sorted order of all node values.

Concept Explanation

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

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

kth smallest in a BST → inorder is sorted
Iterative stack inorder is easy to stop at k steps
Augmenting subtree sizes enables O(log n) with extra memory (not required here)

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — collect all values with any traversal, sort — O(n log n).
Better — full inorder into slice, index k-1 — O(n) time / O(n) space.
Optimal — O(h + k) time (early stop) / O(h) stack — iterative inorder: pop k times; or recursive with shared counter.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func kthSmallest(root *TreeNode, k int) int {
	stack := []*TreeNode{}
	current := root
	remaining := k
	for current != nil || len(stack) > 0 {
		for current != nil {
			stack = append(stack, current)
			current = current.Left
		}
		last := len(stack) - 1
		current = stack[last]
		stack = stack[:last]
		remaining--
		if remaining == 0 {
			return current.Val
		}
		current = current.Right
	}
	return 0
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function kthSmallest(root, k) {
	const stack = [];
	let current = root;
	let remaining = k;
	while (current !== null || stack.length > 0) {
		while (current !== null) {
			stack.push(current);
			current = current.left;
		}
		current = stack.pop();
		remaining--;
		if (remaining === 0) {
			return current.val;
		}
		current = current.right;
	}
	return 0;
}