230. Kth Smallest Element in a BST

At a Glance

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

Problem (one-liner)

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.

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)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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