How do you approach Kth Smallest Element in a BST?

What traversal order visits a BST's values in sorted (ascending) order?

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

Time complexity: O(h + k) - descend to the leftmost node, then visit k nodes. Space complexity: O(h) for the stack.

What are common mistakes on Kth Smallest Element in a BST?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Kth Smallest Element in a BST

MediumData Structures

Description

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) of all the values of the nodes in the tree.

Note: The tree is given as a level-order array where the node at index i has its left child at index 2*i + 1 and its right child at index 2*i + 2, with null for missing nodes (trailing positions may be omitted).

For example, [3, 1, 4, null, 2] represents:

Example 1

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

Output: 1

Example 2

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

Output: 3

Example 3

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

Output: 2

Constraints

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

Kth Smallest Element in a BST: approach, complexity and pitfalls

A medium trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

What traversal order visits a BST's values in sorted (ascending) order?
An in-order traversal (left, node, right) yields values smallest-first - the kth visited node is the answer.
You don't need to traverse the whole tree: stop as soon as you've visited k nodes. An explicit stack makes early exit easy.

The optimal approach

Show the approach: In-Order Traversal with Early Exit

An in-order traversal of a BST visits values in ascending order, so the k-th node visited is the k-th smallest. Use an explicit stack: descend left pushing indices, pop and count, then move into the right subtree. Stop as soon as the counter hits k - no need to finish the traversal.

Time: O(h + k) - descend to the leftmost node, then visit k nodes
Space: O(h) for the stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.