What is the brute force approach and complexity for Kth Smallest Element in a BST?

Inorder walk into an array, then read position k − 1 with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Kth Smallest Element in a BST?

Walk in order with a stack and return the value at the k-th pop with optimal time complexity O(H + k) and space complexity O(H).

How do you identify the pattern for Kth Smallest Element in a BST?

Look for key signals in the prompt: "k-th smallest" indicates We need sorted order. In a BST, an inorder walk gives it.; "k counts from 1" indicates The first pop is k = 1, not the root.; "return only the k-th value" indicates Stop early. Do not build the whole list..

Kth Smallest Element in a BST

Medium·LeetCode #230 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given the root of a binary search tree and an integer k.

Return the k-th smallest value among all node values in the tree. k counts from 1: k = 1 is the smallest value.

Input

The root of a binary search tree with n nodes, and an integer k.

Output

The k-th smallest value in the tree.

Example 1

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

Output: 1

The values in order are 1, 2, 3, 4. The 1st is 1.

Example 2

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

Output: 3

The values in order are 1, 2, 3, 4, 5, 6. The 3rd is 3.

Constraints

• The number of nodes is n
• 1 ≤ k ≤ n ≤ 10^4
• 0 ≤ Node.val ≤ 10^4
• Follow-up: if the tree changes often (inserts and deletes) and k-th queries are frequent, how would you make each query fast?

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“k-th smallest”

→ We need sorted order. In a BST, an inorder walk gives it.

“k counts from 1”

→ The first pop is k = 1, not the root.

“return only the k-th value”

→ Stop early. Do not build the whole list.

Approach Complexity Ladder

Brute Force — write every value into a sorted listO(N)O(N)

Inorder walk into an array, then read position k − 1

Optimal — inorder with a stack, stop at the k-th popO(H + k)O(H)

Walk in order with a stack and return the value at the k-th pop

Brute Force Intuition

An inorder walk gives the values in sorted order. Store all n values in an array, then return the one at index k − 1. The walk visits every node, even though only one value is needed.

Recognition rule for this sub-pattern:

Left < node < right. Inorder is sorted; a valid range (low, high) is passed down.

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture