Kth Smallest Element in a BST

Iterative inorder traversal with early stop

In-order traversal gives sorted order. Can you do it iteratively with a stack?

Published Apr 16, 2026

Problem

Given the root of a BST and an integer k, return the value of the k-th smallest element in the tree (1-indexed).

Input

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

Output

Input

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

Output

Intuition

Inorder traversal of a BST visits nodes in sorted order. That's the whole game. Run an inorder traversal, count nodes as you visit, stop when you hit k.

The iterative version is preferable here because it gives you a clean early stop. Recursion can also short-circuit, but you have to thread a sentinel or throw — both uglier than if (++count == k) return node.val.

The complexity is O(h + k) rather than O(n) because the iterative inorder walks down h nodes to find the leftmost, then visits k - 1 more before stopping. For small k on a deep tree, that's a real win.

Approach

Iterative inorder

TimeO(h + k)

SpaceO(h)

Recommended

The classic stack-based inorder template. Two-phase loop: descend left as far as possible (pushing each node), then pop, visit, descend one step right, and repeat.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        let mut curr = root;
        let mut remaining = k;
        loop {
            while let Some(n) = curr.clone() {
                stack.push(Rc::clone(&n));
                curr = n.borrow().left.clone();
            }
            let node = stack.pop().expect("inorder ended before k-th node");
            remaining -= 1;
            if remaining == 0 {
                return node.borrow().val;
            }
            curr = node.borrow().right.clone();
        }
    }
}

Rust · runnable

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let curr = root;
  while (curr !== null || stack.length > 0) {
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }
    const node = stack.pop()!;
    if (--k === 0) return node.val;
    curr = node.right;
  }
  return -1; // k > tree size; problem guarantees k ≤ size
}

TypeScript · runnable

Recursive inorder with counter

TimeO(h + k)

SpaceO(h)

Same algorithm, recursive shape. A counter and a result variable live in a closure (or as &mut parameters). Once the counter hits zero, all upstream calls short-circuit and the result propagates back.

The recursion is more readable, but the early-stop bookkeeping makes the iterative version slightly cleaner once you've seen it.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
        fn inorder(
            node: Option<Rc<RefCell<TreeNode>>>,
            remaining: &mut i32,
            answer: &mut i32,
        ) {
            if *remaining <= 0 {
                return;
            }
            let Some(n)= node else { return };
            inorder(n.borrow().left.clone(), remaining, answer);
            *remaining -= 1;
            if *remaining= 0 {
                *answer= n.borrow().val;
                return;
            }
            inorder(n.borrow().right.clone(), remaining, answer);
        }
        let mut remaining= k;
        let mut answer= 0;
        inorder(root, &mut remaining, &mut answer);
        answer
    }
}

Rust · runnable

function kthSmallest(root: TreeNode | null, k: number): number {
  let remaining = k;
  let answer = 0;
  const inorder = (node: TreeNode | null): void => {
    if (remaining <= 0 || node === null) return;
    inorder(node.left);
    if (--remaining === 0) {
      answer = node.val;
      return;
    }
    inorder(node.right);
  };
  inorder(root);
  return answer;
}

TypeScript · runnable

Trace

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

Inorder visits values 1, 2, 3, 4, 5, 6 in order. The 3rd is 3.

step	stack after push-left	popped	counter	action
1	[5, 3, 2, 1]	1	2	continue
2	[5, 3, 2]	2	1	continue (right=null)
3	[5, 3]	3	0	return 3

Edge cases

k = 1 — the answer is the leftmost node; the stack only ever pushes h nodes.
k = n — full traversal; degenerates to standard inorder.
Skewed tree — iterative still works cleanly; the recursive version risks stack overflow on extreme inputs.
Duplicates — the problem usually disallows them in BSTs; if allowed, the inorder ordering rule still holds.

Takeaway

Inorder = sorted, for free, on any BST. Once that lands, problems like "kth smallest", "valid BST", "convert BST to sorted DLL", and "two-sum in BST with O(h) extra space" all collapse into variations on the same template. The two-phase iterative inorder is worth memorizing as a unit.

Medium#235

LCA of a BST

Use the BST property to decide which subtree to explore.

Easy#104

Maximum Depth of Binary Tree

1 + max(left_depth, right_depth). This IS the recursive template.

Easy#226

Invert Binary Tree

The simplest recursive tree transformation. Swap left and right, recurse.