Find k-th Smallest Element in BST

Given the root of a binary search tree and an integer k (1 <= k <= number of nodes), return the k-th smallest value in the BST.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

An inorder traversal of a BST yields values in ascending order.

So the k-th smallest is the k-th node you visit inorder.

Use an iterative inorder and stop as soon as you've popped k nodes.

Common doubts

Inorder visits the left subtree (all smaller), then the node, then the right subtree (all larger) — recursively, that's ascending order.

It stops after k pops, so for small k it touches far fewer than n nodes.

Do a reverse inorder (right, node, left) and stop at the k-th pop.

Interview follow-ups

· What an interviewer asks next.

Augment each node with its subtree size; then kth is an O(height) descent using the counts.

Both rely on the inorder-is-sorted property; validate checks it's strictly increasing.

Fun facts

Storing subtree sizes turns kth-smallest into an order-statistics tree query in O(log n).
The iterative inorder here is exactly the mechanism a BST iterator exposes one value at a time.

Asked at

AmazonMicrosoftFacebook

Frequently Sometimes Occasionally

Example 1

Input: root = [5, 3, 6, 2, 4], k = 3
Output: 4
Inorder is 2, 3, 4, 5, 6; the 3rd smallest is 4.

Example 2

Input: root = [5, 3, 6, 2, 4], k = 1
Output: 2
The smallest value.

Constraints

- The number of nodes n is in the range [1, 10^4] - 1 <= k <= n - 1 <= Node.val <= 10^4 - root is a valid BST

An inorder traversal of a BST visits values in ascending order, so the k-th smallest is simply the k-th node of an inorder walk. The optimization: don't build the whole sorted list — do an iterative inorder and stop the moment you've popped k nodes.

Prerequisites

Before you start

· Concepts used directly in the solution.

Inorder = sorted. A BST's inorder traversal is ascending.

Iterative inorder. A stack-based walk you can stop early.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Is k 1-indexed?”

Yes — k = 1 is the smallest value.

“Is k always valid?”

Yes — 1 <= k <= number of nodes.

The ideal opening — say it like this

Inorder gives the BST's values in sorted order, so the k-th smallest is the k-th node I visit inorder.

I do an iterative inorder and return as soon as I've popped k nodes, so I don't traverse the whole tree.

Understand the problem

Worked example — BST [5, 3, 6, 2, 4], k = 3

inorder: 2, 3, 4, 5, 6
3rd smallest = 4

Key observations

1Aha

Inorder is the sorted order

The k-th node visited inorder is exactly the k-th smallest.

2Aha

Stop early

Iterative inorder lets you halt after k pops instead of traversing everything.

3Aha

O(height + k)

You only descend one spine and pop k nodes.

Brute force vs optimal

	Full inorder + index	Iterative inorder, stop at k
Idea	Collect all values, take index k-1	Pop nodes until the k-th
Time	O(n)	O(height + k)
Space	O(n)	O(height)

Both use the sorted-inorder property; the iterative version stops early. Full code is in the Approaches selector below.

Summary

Key takeaway

Inorder yields ascending values, so the k-th smallest is the k-th inorder node. An iterative inorder stops after k pops — O(height + k), O(height) space.

iterative inorder:
    pop the next-smallest node; k -= 1
    if k == 0: return that node's value