Find the Kth Smallest Value in a Binary Search Tree

Problem

Given a binary search tree with distinct integer values, return its kth smallest value, using one-based k.

The tree is represented by parallel arrays: values[i] is node i's value, and left[i] and right[i] are child indices or -1. root is the root index, or -1 for an empty tree.

Function Contract

Implement kthSmallestInBst(values, left, right, root, k) and return the selected integer. Return -1 when the tree is empty or k is outside 1..n.

Constraints & Assumptions

• 0 <= n = len(values) = len(left) = len(right) <= 200,000.
• Child indices are valid or -1; the arrays form one acyclic tree reachable from root.
• Values are distinct signed integers and satisfy the binary-search-tree invariant.
• k is a signed integer and may be invalid.
• A valid tree value may also be -1; the caller uses the validity of k to distinguish the error sentinel.

Clarifying Questions to Ask

• Is k zero-based? No, one-based.
• Are duplicate values possible? No.
• May traversal stop as soon as the answer is found? Yes.
• Can the tree be highly unbalanced? Yes; avoid recursion overflow.

Hint: Use the BST's sorted traversal

An iterative in-order traversal visits values in increasing order. Count visits and return at k.

Examples

• values = [3, 1, 4, 2], left = [1, -1, -1, -1], right = [2, 3, -1, -1], root = 0, k = 1 returns 1.
• With the same tree, k = 3 returns 3.
• An empty tree or k = 0 returns -1.

Evaluation Focus

• Performs in-order traversal and stops after the kth visit.
• Handles invalid k, empty input, and a depth-n tree without recursion failure.
• Runs in O(h + k) time and O(h) auxiliary space for height h.

Extensions to Discuss

1. How do subtree-size fields support frequent kth-smallest queries in O(h) time?
2. Which counters must insertion and deletion update?
3. Why do shared-tree counters become difficult when each tenant sees a different filtered subset?