Overview

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) among all node values in the tree.

Implement kthSmallest(root, k) where root is a tree node with { val, left, right } properties.

Constraints

• The tree has n nodes where 1 ≤ k ≤ n.
• Node values are unique integers.
• Tree nodes have the shape { val: number, left: TreeNode | null, right: TreeNode | null }.
• Aim for $O(H + k)$ time where H is the tree height.

Examples

//     3
//    / \\
//   1   4
//    \\
//     2
kthSmallest(root, 1);  // 1
kthSmallest(root, 3);  // 3

//       5
//      / \\
//     3   6
//    / \\
//   2   4
//  /
// 1
kthSmallest(root, 3);  // 3

Notes

• An in-order traversal of a BST visits nodes in ascending order — the kth node visited is the answer.
• You can do this iteratively with a stack to avoid traversing the entire tree once you've found the kth element.
• Alternatively, a recursive approach with an early-exit counter works well.

Solution

function kthSmallest(root, k) {
  const stack = [];
  let node = root;
  let count = 0;

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

  return -1;
}

Resources

• Kth Smallest Element in a BST — LeetCode
• In-order Traversal — Wikipedia