The O(n) Club: Kth Smallest Element in a BST (Without Losing Your Sanity)

The O(n) Club: Kth Smallest Element in a BST (Without Losing Your Sanity)

⚡ TL;DR

In a Binary Search Tree, just do an in-order traversal: left, root, right. Count nodes as you go and bail when you hit number k—no need to reinvent the sort or summon a heap monster. Thank your ancestors for the BST property and check this Java quickie:

// Basic recursive in-order approach
int count = 0, result = -1;
void inorder(TreeNode node, int k) {
  if (node == null) return;
  inorder(node.left, k);
  if (++count == k) result = node.val;
  inorder(node.right, k);
}

🧠 How Devs Usually Mess This Up

Ah, classic mistakes: Thinking the BST’s already sorted array, so you heapify or run full-blown quickselect (nope). Or traversing every blessed node, even after the kth, as if your GPU craves drama. And don’t forget: assuming balance, forgetting that k can be—surprise!—out of range, and returning results that are only correct in an alternate timeline.

🔍 What’s Actually Going On

Picture your BST as a fancy dinner buffet. The leftmost table has the smallest snacks, the rightmost has the gut-busters, and you visit each in precise order thanks to in-order traversal. Want the kth smallest? Walk the tables (left, root, right), count your plates, and snatch the kth. Morris Traversal is you sneaking through the buffet with invisible tongs—no plate stack, no mess, grim efficiency.

If you need to find kth smallest a lot (think: updating leaderboards, hungry users appearing mid-buffet), augment your nodes with a count of everything below them. Now you’re jumping straight to the k-th course, minimal calories burned!

🛠️ PseudoCode

• Recursive Inorder:
  • Start at root. Visit left child (for smaller numbers).
  • Increment counter upon visiting each node.
  • If counter == k, record answer and bail.
  • Otherwise head right (for bigger numbers).

  int count = 0;
  int result = -1;
  void inorder(TreeNode node, int k) {
    if (node == null) return;
    inorder(node.left, k);
    if (++count == k) result = node.val;
    inorder(node.right, k);
  }

• Iterative/Stack Inorder (for folks who hate recursion):
  • Use a stack, push left children down, pop, count, and bail at k.
• Morris Traversal (Space Houdini):
  • Temporarily thread predecessor’s right pointer, walk without stack/recursion, restore tree.
  • Why? Minimum space (O(1)), maximum flex for interviews.

💻 The Code

// BST node structure
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
 // Recursive in-order with early exit
class Solution {
    private int count = 0;
    private int result = -1;
    public int kthSmallest(TreeNode root, int k) {
        count = 0; result = -1;
        inorder(root, k);
        return result;
    }
    private void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        if (++count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }
}
 // Morris Traversal - for O(1) space
class MorrisSolution {
    public int kthSmallest(TreeNode root, int k) {
        int count = 0;
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                if (++count == k) return curr.val;
                curr = curr.right;
            } else {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr)
                    pred = pred.right;
                if (pred.right == null) {
                    pred.right = curr;
                    curr = curr.left;
                } else {
                    pred.right = null;
                    if (++count == k) return curr.val;
                    curr = curr.right;
                }
            }
        }
        throw new IllegalArgumentException("k is out of bounds");
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• K isn’t magic: If k < 1 or bigger than node count, you'll get a special prize: wrong output, empty return, or—Java favorite—a runtime explosion.
• Unbalanced trees ≠ fast magic: When your BST leans hard (aka a glorified linked list), O(h) is O(n). Don’t blame Java, balance your tree or temper your expectations.
• Recursion depth: Remember, stack overflows aren’t just for websites. Deep trees = “:stack overflow” IRL.
• Stopping too late: Nobody needs to traverse more than k nodes. Don’t code like your CPU enjoys cardio.

🧠 Interviewer Brain-Tattoo

“Walk the tree in order; count to k. The BST’s already sorted—your job is not to make it weird.”
Bonus tip: The less code, the more sleep you get before the interview.