Kth Smallest Element in BST in DSA Typescript

Mental Model

A binary search tree keeps smaller values on the left and bigger on the right. To find the kth smallest, we visit nodes in order from smallest to largest.

Analogy: Imagine a library where books are arranged from left to right by their size. To find the kth smallest book, you start from the smallest on the left and count until you reach the kth one.

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find 3rd smallest element

Goal: Find the 3rd smallest value in the BST

Step 1: Start in-order traversal at root (5), move left to 3

2 -> 3 -> 4 -> 5 -> 7 -> 8
[curr at 3]

Why: Left subtree has smaller values, so we start there to find smallest elements first

Step 2: Move left from 3 to 2, visit 2 (1st smallest)

2 -> [count=1] -> 3 -> 4 -> 5 -> 7 -> 8

Why: 2 is the smallest node, so count 1 here

Step 3: Back to 3, visit 3 (2nd smallest)

2 -> 3 -> [count=2] -> 4 -> 5 -> 7 -> 8

Why: After 2, 3 is next smallest

Step 4: Move right from 3 to 4, visit 4 (3rd smallest)

2 -> 3 -> 4 -> [count=3] -> 5 -> 7 -> 8

Why: 4 is the next smallest, so we found the 3rd smallest

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8
3rd smallest element is 4

Annotated Code

DSA Typescript

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

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let result = -1;

  function inorder(node: TreeNode | null) {
    if (node === null || result !== -1) return;
    inorder(node.left); // traverse left subtree
    count++;
    if (count === k) {
      result = node.val; // found kth smallest
      return;
    }
    inorder(node.right); // traverse right subtree
  }

  inorder(root);
  return result;
}

// Driver code
const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2),
    new TreeNode(4)
  ),
  new TreeNode(7,
    null,
    new TreeNode(8)
  )
);
const k = 3;
console.log(kthSmallest(root, k));

if (node === null || result !== -1) return;

stop traversal if node is null or kth smallest already found

inorder(node.left); // traverse left subtree

visit left subtree first to get smaller values

count++;

increment count when visiting a node

if (count === k) { result = node.val; return; }

when count matches k, record result and stop

inorder(node.right); // traverse right subtree

visit right subtree after current node

Output

4

Complexity Analysis

Time: O(h + k) because we traverse down the tree height h and visit k nodes in order

Space: O(h) due to recursion stack for tree height h

vs Alternative: Naive approach collects all nodes then sorts O(n log n), this uses BST property to do partial traversal O(h + k)

Edge Cases

k is 1 (smallest element)

Returns the smallest node value by visiting leftmost node

DSA Typescript

if (count === k) { result = node.val; return; }

k equals number of nodes (largest element)

Returns largest node value after full in-order traversal

DSA Typescript

if (count === k) { result = node.val; return; }

Empty tree (root is null)

Returns -1 as no nodes exist

DSA Typescript

if (node === null || result !== -1) return;

When to Use This Pattern

When asked for kth smallest or kth largest in a BST, use in-order traversal because it visits nodes in sorted order.

Common Mistakes

Mistake: Not stopping traversal after finding kth smallest, causing unnecessary work
Fix: Add a check to stop recursion once kth smallest is found (result !== -1)

Mistake: Using pre-order or post-order traversal which does not guarantee sorted order
Fix: Use in-order traversal to visit nodes in ascending order

Summary

Finds the kth smallest element in a binary search tree using in-order traversal.

Use when you need the kth smallest value without sorting all nodes explicitly.

In-order traversal visits nodes in ascending order, so counting nodes visited gives the kth smallest.