Kth Smallest Element in a BST

Why it belongs on this sheet

This is a practical BST question that rewards understanding in-order traversal order.

Pattern

Inorder gives sorted order

Approach

Traverse the BST in inorder. Each visited node is the next smallest element, so decrement k until it reaches zero.

Java solution

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
  public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
      while (current != null) {
        stack.push(current);
        current = current.left;
      }

      current = stack.pop();
      if (--k == 0) {
        return current.val;
      }

      current = current.right;
    }

    return -1;
  }
}

Complexity

• Time: O(h + k) on average
• Space: O(h)

Interview note

The iterative solution is a good way to show traversal control without extra arrays.