Kth Smallest Element in a BST · Interview Problem

Back to problems

Leetcode

Medium

Trees

Recursion

Stacks

Binary Search

Google

Amazon

Microsoft

Kth Smallest Element in a BST

Return the $k$ -th smallest value in a binary search tree.

Acceptance 100%

Start Practice

Problem Statement

Problem

Given the root of a binary search tree (BST) and an integer $k$ , return the value of the $k$ -th smallest node in the tree.

A BST has the property that for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

You may assume that $k$ is valid and there is exactly one answer.

Input Format

The root of a BST.
An integer $k$ .

Output Format

Return the value of the $k$ -th smallest node in the BST.

Constraints

The tree is a valid BST.
$1 \le k \le n$ , where $n$ is the number of nodes in the tree.
Node values are distinct.

Hints

In a BST, an in-order traversal visits nodes in sorted order.
You do not need to traverse the entire tree if you can stop once the answer is found.

Input Format

root: root node of a valid binary search tree
k: a valid positive integer

Output Format

The value of the $k$ -th smallest node in the BST

Constraints

Valid BST
Distinct node values
$1 \le k \le n$

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

Explanation

The in-order traversal is [1,2,3,4]. The 1st smallest value is 1.

Example 2

Input

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

Output

Explanation

The in-order traversal is [1,2,3,4,5,6]. The 3rd smallest value is 3.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress