Kth Smallest Element in a BST

Problem

Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest element (1-indexed) among all node values in the tree.

Recall that a BST has the property that for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

Input / Output Format

Input:

• root — the root of a BST represented as a level-order (BFS) array where null indicates a missing node.
• k — an integer indicating which smallest element to find (1-indexed).

Output:

• An integer — the kth smallest value in the BST.

Examples

Example 1

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

    3
   / \
  1   4
   \
    2

Output: 1

Explanation: The in-order traversal of this BST is [1, 2, 3, 4]. The 1st smallest element is 1.

Example 2

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

        5
       / \
      3   6
     / \
    2   4
   /
  1

Output: 3

Explanation: The in-order traversal is [1, 2, 3, 4, 5, 6]. The 3rd smallest element is 3.

Example 3

Input: root = [2,1,3], k = 2

  2
 / \
1   3

Output: 2

Explanation: The in-order traversal is [1, 2, 3]. The 2nd smallest element is 2.

Approach Hints

• Key Insight: In a BST, an in-order traversal (left → root → right) visits nodes in ascending sorted order. The kth element visited during this traversal is the answer.
• Recursive DFS: Perform an in-order traversal while counting visited nodes. Stop and return the value when the counter reaches k.
• Iterative with Stack: Use an explicit stack to simulate in-order traversal without recursion. This is memory-efficient for very deep trees and allows early termination.
• Follow-up (Bonus): If the BST is frequently modified (insertions/deletions) and you need to find the kth smallest often, how would you optimize? Think about augmenting each node with a subtree size count.