kth-smallest-bst.ts

import { TreeNode } from "../lib/tree-node.js";

/**
 * 230. Kth Smallest Element in a BST  (Medium)
 * Link: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
 *
 * Given the root of a BST and an integer k (1-indexed), return the kth smallest
 * value in the tree.
 *
 * Example:
 *   Input:  root = [3,1,4,null,2], k = 1
 *   Output: 1
 *
 * Approach:
 *   An in-order traversal of a BST visits values in ascending order. Walk
 *   in-order with an explicit stack, decrementing k as each node is visited;
 *   when k hits 0 the current node is the answer, so we can stop early without
 *   traversing the whole tree.
 *
 * Time:  O(h + k)  — descend then visit k nodes.
 * Space: O(h)      — the stack.
 */
export function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let node = root;

  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    if (--k === 0) return node.val;
    node = node.right;
  }

  throw new Error("k is larger than the number of nodes in the tree.");
}