Kth Smallest Element in a BST

Mediumtreebinary-search-treein-order-traversal
Category: Trees
Companies that ask this question:
AmazonGoogleFacebookMicrosoft
LeetCode →NeetCode →

Approach

Kth Smallest Element in a BST

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 in the tree.

Examples

Example 1

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

Tree:
    3
   / \
  1   4
   \
    2

In-order: [1, 2, 3, 4]
1st smallest = 1

Example 2

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

Tree:
        5
       / \
      3   6
     / \
    2   4
   /
  1

In-order: [1, 2, 3, 4, 5, 6]
3rd smallest = 3

Intuition

Key BST Property: In-order traversal visits nodes in sorted order!

For BST, in-order traversal produces: left → root → right = sorted sequence.

To find kth smallest:

  1. Do in-order traversal
  2. Count nodes visited
  3. Return the kth node

We can optimize by stopping early once we reach k nodes.

Pattern Recognition

This is an In-order Traversal problem with:

  • BST property exploitation
  • Early termination optimization
  • Counting during traversal

Approach

In-order DFS with Counter

  1. Initialize: counter = 0, result = None

  2. In-order Traversal:

    inorder(node):
  if not node: return
  inorder(node.left)    # Visit left
  counter++             # Process current
  if counter == k:
    result = node.val
    return
  inorder(node.right)   # Visit right

  3. Return result

Optimization: Stop recursion once k is reached (no need to visit remaining nodes).

Iterative with Stack (Alternative)

stack = []
current = root
count = 0

while current or stack:
  while current:
    stack.append(current)
    current = current.left
  current = stack.pop()
  count += 1
  if count == k:
    return current.val
  current = current.right

Edge Cases

  • k = 1 (smallest element)
  • k = n (largest element)
  • Single node tree
  • Skewed tree (all left or all right)
  • k equals number of nodes

Complexity Analysis

Recursive In-order

  • Time: O(h + k) where h = height

    • O(h) to reach leftmost node
    • O(k) to find kth node
    • Best case: O(k) if balanced
    • Worst case: O(n) if k = n or skewed tree

  • Space: O(h) recursion stack

    • O(log n) for balanced tree
    • O(n) for skewed tree

Naive Approach (Store All)

  • Time: O(n) - visit all nodes
  • Space: O(n) - store all values

Optimized approach is better when k is much smaller than n.

Solution

java
1class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14class Solution {
15    private int count = 0;
16    private int result = 0;
17
18    public int kthSmallest(TreeNode root, int k) {
19        inorder(root, k);
20        return result;
21    }
22
23    private void inorder(TreeNode node, int k) {
24        if (node == null || count >= k) {
25            return;
26        }
27
28        // Visit left subtree
29        inorder(node.left, k);
30
31        // Process current node
32        count++;
33        if (count == k) {
34            result = node.val;
35            return;
36        }
37
38        // Visit right subtree
39        inorder(node.right, k);
40    }
41}
42
Loading visualizer...