How do you find the kth smallest element in a BST?

Question presented to candidate: "Given the root of a binary search tree and an integer k, write a Python function that returns the kth smallest value in the tree (k is 1-indexed). Then tell me what you would change if the tree is modified often and kth-smallest is asked many times."

What a strong answer should cover:

• In-order traversal of a BST visits values in sorted order, so the kth visited node is the answer.
• Stop early: an iterative in-order walk with an explicit stack costs O(h + k) time and O(h) space instead of O(n).
• The simple version (collect the whole in-order list, return index k − 1) is O(n) time and O(n) space — correct, but wasteful.
• The follow-up: store a subtree size in every node (an order-statistic tree) so each query is one root-to-node walk, O(h), and updates keep sizes current.
• Invalid k (k < 1 or k > n) and what to return.
• Python specifics: a list as the stack; a generator with yield from plus itertools.islice is a neat lazy alternative, but recursive generators still hit the recursion limit on deep trees.

Clarifying questions expected:

• Is k always between 1 and the number of nodes?
• Will the tree be modified between queries, and how many queries will there be?

Code / implementation expected: Yes — an iterative in-order walk with a list as the stack, in Python 3.