Difficulty: MediumTrees

Kth Smallest Element in a BST

Problem in Plain English

Given the root of a binary search tree and an integer k, return the kth smallest value using the fact that an inorder walk visits values in ascending order. Every k between 1 and the tree size is valid.

Problem Statement

Given the root of a binary search tree and an integer k, return the kth smallest value in the tree, counting from 1.

A binary search tree keeps smaller values on the left and larger values on the right, so an inorder walk of left, node, then right visits values in strictly increasing order.

Constraints

1 <= k <= n <= 10^4, where n is the number of nodes
0 <= Node.val <= 10^4
The tree is a valid binary search tree

Examples

Example 1

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

Inorder gives [1,2,3,4,5,6]. Counting from one, the visits are 1, then 2, then 3, so rank three returns 3. The root value is not its rank.

Example 2

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

Inorder gives [1,2,3,4], so rank one returns 1. Its right child 2 comes after 1; early stopping returns before entering that right subtree.

Example 3

Input: root = [0], k = 1
Output: 0

A single node is both the smallest and largest value. Rank one returns 0; zero is a valid answer, not a missing-node marker.

Example 4

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

This right-only chain has inorder [1,2,3,4]. Since k equals the node count, early stopping must visit every node before returning 4.

Intuition

A rank is a position in sorted order, not a distance from the root. In a binary search tree, every left-subtree value is smaller than its root and every right-subtree value is larger. Visiting left subtree, node, then right subtree therefore produces sorted values without sorting. In Example 1, this order is [1,2,3,4,5,6]; the third visit is 3, although the root is 5. A stack remembers ancestors waiting for their left subtrees to finish. We can either collect all values or count visits and stop at the requested rank.

Approaches

Full Inorder Collect

Solution Details

Reveal Full Inorder Collect: intuition, complexity, and code

Intuition

Materialize the sorted inorder sequence, then select index k - 1. An explicit stack performs the same left, node, right walk as recursion without risking call-stack overflow on a long chain. Example 1 collects [1,2,3,4,5,6], making the answer at index 2 easy to see, but storing and visiting every value is unnecessary for a small rank.

Step-by-Step Logic

Initialize empty order and stack, and point curr at the root. Example 1 begins at 5 with k = 3.
Push the current node and move left repeatedly, deferring ancestors until smaller values finish. Example 1 pushes 5, 3, 2, 1.
When the left descent ends, pop the next node, append its value and move to its right child. Example 1 first appends 1, whose right child is null.
Repeat until both current pointer and stack are empty. Example 1 appends 2, 3, 4, 5, 6; entering the right child of 3 ensures 4 precedes 5.
Read index k - 1 after the full walk. Example 1 reads index 2 from [1,2,3,4,5,6] and returns 3.

Why It Works

A node is pushed before its left descendants and popped only after those descendants have been visited. Appending it before entering its right subtree therefore follows left, node, right order. By induction on subtrees, each left subtree produces sorted smaller values, then its root is appended, then its right subtree produces sorted larger values. Every node is pushed and popped once, so the resulting list contains every value exactly once in increasing order. Its zero-based index k - 1 consequently holds the one-based kth value. Child references and values are only read, preserving the tree.

Dry Run

Full Inorder Collect: variable states at each step
Action	curr after action	Stack bottom to top	order
Initialize	`5`	`[]`	`[]`
Push 5, move left	`3`	`[5]`	`[]`
Push 3, move left	`2`	`[5,3]`	`[]`
Push 2, move left	`1`	`[5,3,2]`	`[]`
Push 1, move left	null	`[5,3,2,1]`	`[]`
Pop 1, append, move right	null	`[5,3,2]`	`[1]`
Pop 2, append, move right	null	`[5,3]`	`[1,2]`
Pop 3, append, move right	`4`	`[5]`	`[1,2,3]`
Push 4, move left	null	`[5,4]`	`[1,2,3]`
Pop 4, append, move right	null	`[5]`	`[1,2,3,4]`
Pop 5, append, move right	`6`	`[]`	`[1,2,3,4,5]`
Push 6, move left	null	`[6]`	`[1,2,3,4,5]`
Pop 6, append, move right	null	`[]`	`[1,2,3,4,5,6]`
Loop ends; read index 2	null	`[]`	Return `3`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the node count and h the height in nodes. Each node is pushed, popped and appended once, taking O(n) time with amortized list growth. The list stores n values and the stack holds at most h existing-node references: O(n + h) = O(n) auxiliary space. Java also boxes list integers; no TreeNode is copied or allocated. The scalar output uses O(1) space. Iteration avoids recursion-depth limits even when h = n.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Deque;3import java.util.ArrayList;4import java.util.List;5
6class TreeNode {7    int val;8    TreeNode left, right;9    TreeNode(int val) { this.val = val; }10}11
12class Solution {13    public int kthSmallest(TreeNode root, int k) {14        List<Integer> order = new ArrayList<>();15        Deque<TreeNode> stack = new ArrayDeque<>();16        TreeNode curr = root;17        while (curr != null || !stack.isEmpty()) {18            // Defer ancestors until their smaller left-subtree values have been visited.19            while (curr != null) {20                stack.push(curr);21                curr = curr.left;22            }23            curr = stack.pop();24            order.add(curr.val);25            curr = curr.right;26        }27        // Convert the one-based rank to a zero-based list index.28        return order.get(k - 1);29    }30}

Hints

Hint 1

Which traversal of a BST visits values in sorted order? A breadth-first walk does not preserve ranks.

Hint 2

Think of k as the number of inorder visits needed, rather than a target value or root depth.

Hint 3

Keep ancestors on a stack while moving left; pop one visit, then move right. Count only pops and return immediately on visit k.

Edge Cases

A single node with value 0 and k = 1 returns 0; test nodes for null rather than testing their values.
For k = 1, return the leftmost value. A 10,000-node left chain still requires 10,000 pushes before the first pop.
For k = n, the answer is the rightmost value and every node is visited, so early stopping saves no visits.
Left-only and right-only chains are valid BSTs. Explicit stacks handle their maximum height without recursive call-stack limits.
Rank can fall on an internal node with a right child, as 3 does in Example 1. Return before traversing that larger subtree.

Common Mistakes and Interview Tips

Using order[k] instead of order[k - 1] confuses one-based ranks with zero-based indices.
Incrementing the counter on push counts deferred ancestors before smaller descendants; Example 1 would count root 5 first.
Moving right before visiting the popped node changes inorder to left, right, node and destroys sorted order.
Claiming O(k) time ignores the initial left descent: k = 1 on a left chain takes O(n). Claiming O(log n) stack space assumes balance, which is not guaranteed.
Using recursive collection without discussing runtime limits can fail on the allowed 10,000-node chain. The published collectors use explicit stacks.
Keeping count or collected values on the Solution object without resetting them corrupts repeated calls. These snippets use invocation-local state.
For repeated updates and rank queries, augment each node with its subtree size. Compare k with left size + 1 to choose a branch; subtract left size + 1 when moving right. Maintain sizes through insertions, deletions and rotations. Queries take O(h), becoming O(log n) only with balance.

Key Takeaway

A BST turns inorder traversal into a sorted stream. An explicit stack preserves the next visit without copying or modifying the tree, and a rank query can stop after k visits. This shortcut relies on the BST property; arbitrary binary trees do not have sorted inorder values.