Binary Search Tree Kth Smallest Element

You're given the root of a binary search tree (BST) and a number k. Return the value of the k-th smallest element, counting from 1. A BST is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger — which means the tree already encodes a sorted order, you just have to read it out. Think of a leaderboard stored as a BST: "who's in 3rd place?" is exactly this question.

Signature

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

// k is 1-indexed: k = 1 asks for the smallest value, k = 2 the second smallest, ...
function binarySearchTreeKthSmallest(root: TreeNode | null, k: number): number;

Examples

//        5
//       / \
//      3   7
//     / \   \
//    2   4   8
//
// Sorted order (in-order): 2, 3, 4, 5, 7, 8
binarySearchTreeKthSmallest(root, 1); // 2  — the smallest

//        5
//       / \
//      3   7
//     / \   \
//    2   4   8
//
binarySearchTreeKthSmallest(root, 3); // 4  — third smallest
binarySearchTreeKthSmallest(root, 6); // 8  — the largest (size is 6)

Notes

• k is 1-indexed — k = 1 returns the smallest value, not the second-smallest. There is no k = 0.
• The tree is a valid BST — left subtree values are strictly less than the node, right subtree values strictly greater. You can rely on this; you don't have to verify it.
• k is always valid — 1 ≤ k ≤ number of nodes. You won't be asked for the 10th smallest of a 6-node tree.
• Node shape is { val, left, right } — missing children are null, not undefined.
• In-order traversal of a BST yields values in sorted order — that's the entire insight. The k-th node you visit in-order is the answer.