Full lesson preview

Find the kth smallest element in a BST

Return the kth smallest value in a BST using an efficient in-order traversal.

Python practice15 minTrees & Binary TreesIntermediateLast updated March 29, 2026

Problem statement

Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest element's value (1-indexed). If k is out of bounds (less than 1 or greater than the number of nodes), return None.

Task

Implement a function to find the kth smallest element in a BST. Handle invalid k by returning None.

Examples

Find 3rd smallest

Input

root = build_bst([5,3,7,2,4,6,8]); k = 3 result = kth_smallest(root, 3)

Output

Inorder traversal gives [2,3,4,5,6,7,8]; the 3rd element is 4.

Input format

Function kth_smallest(root, k) where root is a BST root (or None) and k is an integer.

Output format

Return the integer value of the kth smallest node, or None if k is invalid.

Constraints

- Do not convert the entire tree to a sorted list if possible (aim for O(h + k) time and O(h) space where h is tree height). - k is 1-indexed.

Samples

Sample 1

Input

kth_smallest(build_bst([5,3,7,2,4,6,8]), 1)

Output

Smallest element is 2.