230. Kth Smallest Element in a BST

At a Glance

• Topic: Tree
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 230

Problem Statement

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

Example 1:

Input: root = [3,1,4,null,2], k = 1 Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Approach & Solution Steps

Perform an Inorder Traversal. A BST inorder traversal visits nodes in sorted order. Stop when you reach the kth node.

Optimal JS Solution

function kthSmallest(root, k) {
  let res = null;
  function inorder(node) {
    if (!node || res !== null) return;
    inorder(node.left);
    k--;
    if (k === 0) {
      res = node.val;
      return;
    }
    inorder(node.right);
  }
  inorder(root);
  return res;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.