Iterative in-order

int kthSmallest(Node root, int k) {
  Deque stack = new ArrayDeque<>();
  Node cur = root;
  while (cur != null || !stack.isEmpty()) {
    while (cur != null) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    if (--k == 0) return cur.val;
    cur = cur.right;
  }
  return -1;
}
Advertisement

Recursive with counter

int count = 0, result = 0;
void inorder(Node n, int k) {
  if (n == null || count >= k) return;
  inorder(n.left, k);
  if (++count == k) { result = n.val; return; }
  inorder(n.right, k);
}
Advertisement

Augmented tree — O(log N)

Store size of subtree at each node. Compare size(left) to k → descend left, right, or stop. O(log N) query but requires size maintenance on insert/delete.

Order statistic tree

Formalized: augmented BST supporting rank + select in O(log N). Used in DBs, Redis sorted set (via skip list).