Skip to content

Volume ITechnology

4.14.12 — Kth Smallest Element in a BST ​

LeetCode 230 · Medium · ★ Blind 75

The problem ​

Return the k-th smallest value in a binary search tree, counting from 1.

     3
   / \
  1   4        k = 1  →  1
   \
    2
    2

To put this in plain English: you are given a binary search tree. If you were to list out all the numbers in the tree from smallest to largest, which number would be exactly at the k-th position? (1-indexed, so k=1 is the smallest).

Constraints to Keep in Mind: ​

  • 1 <= k <= Number of nodes in the tree <= 10^4
  • 0 <= Node.val <= 10^4
  • The tree can be heavily unbalanced.

The brute force, and where it wastes work ​

The simplest way is to collect all the values into an array, sort the array, and grab the k-1 index.

  • How it works: You run any traversal (preorder, postorder, etc.), append every node's value to a list, call .sort() on the list, and return list[k-1].
  • Why it's too slow: Sorting takes O(n \log n) time, and storing all elements takes O(n) space. Even if you use an in-order traversal to skip the sorting step (since in-order on a BST yields sorted values automatically), building the full array still takes O(n) time and O(n) space. We don't want to process all n nodes if k is small. We want to stop exactly when we hit the k-th node.

The pattern ​

One fact does all the work:

An in-order traversal of a binary search tree visits the values in increasing order.

Left subtree, then the node, then the right subtree. Because everything on the left is smaller and everything on the right is larger, that order is sorted by construction.

So the k-th smallest is simply the k-th node visited in order. Walk in order, count, and stop at k.

The stopping matters. Collecting every value into a list and indexing works and is O(n) time and space; stopping early makes it O(h + k), which is much better when k is small.

The solution ​

python
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []  # (1)
        node = root

        while stack or node:  # (2)
            while node:                 # (3) go as far left as possible
                stack.append(node)
                node = node.left

            node = stack.pop()          # (4) this is the next value in order
            k -= 1  # (5)
            if k == 0:
                return node.val

            node = node.right           # (6) then explore its right subtree
ts
function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];  // (1)
  let node = root;

  while (stack.length || node) {  // (2)
    while (node) {  // (3)
      stack.push(node);
      node = node.left;
    }

    node = stack.pop()!;  // (4)
    if (--k === 0) return node.val;  // (5)

    node = node.right;  // (6)
  }

  return -1;
}

Line by line ​

(1) A stack of nodes we still owe a visit to, and a pointer node that starts at the root. In a search tree, the smallest value is the leftmost node, so we will head left first.

(2) Keep going while there is a node to explore, or one waiting on the stack.

(3) Dive left as far as possible, pushing every node we pass. Each pushed node is smaller than its ancestors but bigger than everything in its own left subtree, so it must wait until that left subtree has been visited.

(4) Pop the next node in sorted order. When the dive hits a missing left child, the node on top of the stack has nothing smaller left unvisited. So it is the next value in increasing order.

(5) Count it. k -= 1 uses up one of the k values we need. When k reaches 0, this node is the k-th smallest, so return it. TypeScript writes this as --k === 0, which subtracts 1 first and then compares.

(6) Move to its right subtree. Everything there is bigger than this node but smaller than the ancestors still on the stack, so it comes next in order.

The iterative in-order walk is worth learning as a shape, because it is the only traversal where the iterative version is genuinely useful — it lets you stop mid-walk, which recursion cannot do cleanly.

Read it as three steps repeating:

  1. Dive left, pushing every node you pass. The stack now holds the chain of ancestors you will come back to.
  2. Pop. That node is next in sorted order, because everything smaller than it has already been visited.
  3. Turn right and repeat, which handles its right subtree before returning to the ancestors on the stack.

The stack is doing exactly what the call stack would do in the recursive version — holding the nodes you still owe a visit to.

Hand Trace ​

Trace on the example tree:

     3
   / \
  1   4
   \
    2

Find k = 3.

  • Start: node = 3, stack = [].
  • Dive left: push 3, node = 1. push 1, node = null. stack = [3, 1].
  • Pop 1: node = 1. k becomes 2. Next node = 1.right = 2. stack = [3].
  • Dive left: push 2, node = null. stack = [3, 2].
  • Pop 2: node = 2. k becomes 1. Next node = 2.right = null. stack = [3].
  • Dive left: node = null, loop skipped.
  • Pop 3: node = 3. k becomes 0. Target found!
  • Return 3. ✓

Order of pops: 1, 2, 3, 4. Sorted. ✓

The recursive version ​

python
def kthSmallest(self, root, k):
    self.k = k
    self.answer = None

    def inorder(node):
        if not node or self.answer is not None:
            return
        inorder(node.left)
        self.k -= 1
        if self.k == 0:
            self.answer = node.val
            return
        inorder(node.right)

    inorder(root)
    return self.answer

Shorter, but the early exit needs a guard at the top of every call, because a return only leaves one frame. That awkwardness is exactly why the iterative version is preferred here.

Complexity ​

  • Time Complexity: O(h + k). To find the first (smallest) element, we must traverse down to the leftmost leaf, which takes O(h) steps where h is the tree's height. Then we pop and process k nodes. So total time is proportional to h + k. If the tree is balanced, h \approx \log n. If k is small, this is highly efficient. If k \approx n, it degrades to O(n).
  • Space Complexity: O(h). The maximum size of the stack at any given time is the length of a single path from the root down to a leaf, which is the height of the tree h. No additional space is needed.

Edge cases ​

  • k = 1. The answer is the leftmost node, found after the first dive.
  • k equals the number of nodes. The answer is the largest value, the last node popped.
  • A tree shaped like a line going left. The first dive pushes every node, so the stack grows to n.
  • A tree shaped like a line going right. The stack never holds more than one node.

The follow-up that matters ​

"What if the tree is modified often and you need this frequently?"

Walking the tree for every query is O(h + k) each time, which is wasteful when queries are common. The answer is to augment the tree: store in each node the size of its subtree.

Then finding the k-th smallest becomes a single root-to-leaf walk:

let L = size of the left subtree
if k <= L        → the answer is in the left subtree
if k == L + 1    → this node is the answer
otherwise        → go right, looking for the (k − L − 1)-th

That is O(h) per query, with no dependence on k at all. The cost is maintaining the sizes on insertion and deletion, which is O(h) per update, since only the nodes along one path change.

This is a genuinely important idea: storing an aggregate in each node so that queries become walks. It is how order-statistic trees work, and it is the same technique behind segment trees and Fenwick trees in 4.13.4.

Where this goes next ​

  • Kth Largest Element in a BST — reverse in-order: right, node, left.
  • Range Sum of BST — prune whole subtrees that fall outside the range, using the ordering.
  • BST Iterator (LeetCode 173) — this exact stack, exposed as next() and hasNext(). It is O(1) amortized per call and O(h) space, which is the same argument as the monotonic stack in 4.8: each node is pushed once and popped once.

What the interviewer will push on ​

"Why does in-order give sorted output?" Left is smaller, right is larger, so visiting left–node–right is sorted by construction.

"Why iterative rather than recursive?" Stopping early is clean; with recursion you need a guard in every frame.

"What if the tree changes often?" Augment nodes with subtree sizes for O(h) queries.

"What if you needed the k-th largest?" Reverse the traversal.

One thing to volunteer: say the in-order fact out loud before writing anything, and note that you will stop at k rather than collect everything.

Next: 4.14.13 Construct Binary Tree from Preorder and Inorder — going backwards, from traversals to the tree.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet