Kth Smallest Element in BST in DSA Javascript

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 by size from left to right. To find the kth smallest book, you start from the smallest shelf and count books in order until you reach k.

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑ (root)

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
 ↑ visiting 2 next

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

Step 2: Visit node 2 (smallest), count = 1

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

Why: First smallest element found at node 2

Step 3: Move up to node 3, count = 2

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

Why: Second smallest element found at node 3

Step 4: Move right to node 4, count = 3

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

Why: Third smallest element found at node 4, stop traversal

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8
Answer: 4

Annotated Code

DSA Javascript

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

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (!node || result !== null) return;

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

    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 || result !== null) return;

stop traversal if node is null or kth smallest already found

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

explore smaller values first by going left

count++;

increment count when visiting a node in order

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

check if current node is kth smallest and save result

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

explore larger values after left and 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 sorts all nodes O(n log n), this uses BST property to stop early at kth node

Edge Cases

k is larger than number of nodes

function returns null because kth smallest does not exist

DSA Javascript

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

BST with single node and k=1

returns the single node value correctly

DSA Javascript

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

BST with duplicate values

counts duplicates as separate nodes in order

DSA Javascript

count++;

When to Use This Pattern

When a problem asks for the kth smallest or largest element 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 result is found (result !== null)

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 by visiting nodes in ascending order using in-order traversal.

Use when you need the kth smallest value in a binary search tree efficiently.

The key insight is that in-order traversal of BST visits nodes from smallest to largest.