Kth Smallest in a BST

Difficulty: Medium · Topic: Trees

Build a BST from the insertion list values, then return the k-th smallest value (1-indexed). The key fact: an in-order traversal of a BST visits values in ascending order, so the k-th visited node is the answer.

Examples

kth_smallest_bst([5,3,8,2,4,7], 1)
→ 2

Sorted: 2,3,4,5,7,8 → 1st is 2.

kth_smallest_bst([5,3,8,2,4,7], 3)
→ 4

kth_smallest_bst([5,3,8,2,4,7], 6)
→ 8

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.