leetExpert
Practice

Kth Smallest Element in a BST

Module 18 · BST & Ordered Structures

Problem

Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree (1-indexed — k = 1 is the minimum).

Examples

Example 1

Inputroot = [3,1,4,null,2], k = 1Output1

Example 2

Inputroot = [5,3,6,2,4,null,null,1], k = 3Output3
text
      3                5
     / \              / \
    1   4            3   6
     \              / \
      2            2   4
                  /
                 1

Constraints

1 ≤ k ≤ n ≤ 10⁴ · node values are distinct

Attempt it first

You proved something in the first concept lesson that makes this problem almost fall open by itself — recall what an inorder traversal of a BST produces. Before writing anything, state what the k-th smallest element is in terms of that traversal, and then think about whether you actually need to finish the traversal to find it.