Kth Smallest Element in a BST

Return the k-th smallest value (1-indexed) in a binary search tree.

A way to picture it

A BST is a library shelf wearing a disguise: read it left, middle, right and the books come out in sorted order. Walk that route and count the books until you reach number k.

How to approach it

An inorder traversal visits BST values in ascending order. Do it iteratively with a stack and stop at the k-th visit.

Example

Input: {"root":[3,1,4,null,2],"k":1}. Output: 1.

Complexity: O(h + k) time and O(h) space. Slide down to the minimum, then take k steps.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.