Kth Smallest Element in a BST

Find the k-th smallest value (1-based) in a binary search tree.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input:

• line 1: the BST
• line 2: k

Output: the k-th smallest value.

Constraints: 1 ≤ k ≤ nodes ≤ 10⁴, values are distinct. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: the inorder traversal of a BST visits values in sorted order — stop after k nodes. With an iterative stack you never visit more than height + k nodes.