Kth Smallest Element in a BST

Given a BST and an integer k, return the k-th smallest value in the tree (1-indexed).

Example

Input: 3 1 4 null 2, k = 1 Output: 1

Approach

An in-order traversal of a BST (left, node, right) visits values in strictly ascending order — a direct consequence of the BST property. So the k-th smallest is simply the k-th value visited during an in-order walk; stop early once you've collected k values instead of always walking the whole tree.

Input format

Line 1: the tree in level-order, space-separated, null for missing children Line 2: k

Print the k-th smallest value.