Why does inorder traversal find the kth smallest element?

In a binary search tree every left subtree holds smaller values and every right subtree larger ones, so visiting left subtree, node, right subtree lists the values in ascending order. The k-th node visited is the k-th smallest.

What is the time complexity of Kth Smallest Element in a BST?

O(h + k): the walk first descends the left spine, h nodes for a tree of height h, then pops k nodes, each with at most a short detour right and left. In the worst case that is O(n). The stack holds at most h nodes, so space is O(h).

Why use an iterative stack instead of recursion?

The stack makes stopping early trivial — return as soon as the k-th node is popped — without threading a counter and a found flag through recursive calls. Both visit the same nodes in the same order.

Kth Smallest Element in a BST

Find the k-th smallest value in a binary search tree by walking it in order — ascending — and stopping at the k-th node.

MediumSolve on LeetCode

Problem Understanding

Kth Smallest Element in a BST: given the root of a binary search tree and an integer k, return the k-th smallest value in the tree (1-indexed). k is between 1 and the number of nodes.

Example: root = [5, 3, 6, 2, 4, null, null, 1], k = 3 returns 3 — the values in order are 1, 2, 3, 4, 5, 6.

Attempt 1: Collect and Sort

Visit every node, collect the values, sort them and return index k − 1: O(n log n) time and O(n) space. It ignores the one thing a BST gives you for free — its values are already ordered.

The Intuition: Inorder Is Already Sorted

In a binary search tree, everything in a node's left subtree is smaller and everything in its right subtree is larger. So an inorder walk — left subtree, node, right subtree — visits values in ascending order, with no sorting needed.

The k-th node an inorder walk visits is the answer, and the walk can stop there. Doing it with an explicit stack makes stopping easy:

Go left: push every node on the way down the left side.
Pop: the top of the stack is the smallest value not yet visited. Count it; if it is the k-th, return it.
Go right: move to its right child and repeat.

This is the same depth-first inorder traversal, written as a loop.

Interactive Walkthrough

Nodes waiting on the stack are marked as the walk dives left. Each pop fills its node and labels it with its rank — #1, #2, #3 — which always reads in ascending value. The walk stops at rank k.

Dry Run Table

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

Step	Action	Stack (top last)	Popped so far	`k` left
1	Push 5, 3, 2, 1 going left	`[5, 3, 2, 1]`	—	3
2	Pop 1 (no right child)	`[5, 3, 2]`	`1`	2
3	Pop 2 (no right child)	`[5, 3]`	`1, 2`	1
4	Pop 3	`[5]`	`1, 2, 3`	0

The third pop is 3, so return 3. Nodes 4, 5 and 6 are never visited.

The Solution Template

Iterative inorder traversal that stops at the k-th pop.

Kth Smallest Element in a BST Code

1var kthSmallest = function(root, k) {
2    const stack = [];
3    let node = root;
4    while (true) {
5        while (node) {
6            stack.push(node);
7            node = node.left;
8        }
9        node = stack.pop();
10        k--;
11        if (k === 0) {
12            return node.val;
13        }
14        node = node.right;
15    }
16};

Edge Cases & Common Mistakes

k = 1: the leftmost node — the walk pops it straight after the first dive.
k = n: the largest value; every node is visited.
A tree leaning right ([1, null, 2, null, 3]): the stack never holds more than one node.
Off-by-one: k is 1-indexed, so decrement before comparing with 0, or compare a 1-based counter with k.
Sorting the values: correct but O(n log n) — the inorder order is already sorted.
Follow-up — frequent queries on a changing tree: store each node's subtree size, then pick left or right by comparing k with the left subtree's size, in O(h) per query.

Summary

Inorder traversal visits a BST in ascending order, so the k-th node it visits is the answer. Walk it with a stack and stop at the k-th pop: O(h + k) time, O(h) space.

Validate Binary Search Tree

Construct Binary Tree from Preorder and Inorder Traversal