← Back to problems
UNSW COMP2521 · medium

BST: k-th Smallest

BST: k-th Smallest

Insert n distinct integers into a BST in input order; print the k-th smallest value.

Key: an in-order traversal of a BST is ascending. The k-th visited node is the answer.

Input: line 1 n k; line 2 n integers. Output: the k-th smallest value.

Example: 5 2 / 50 30 70 20 40 -> 30.