Binary Search Tree Internals — Validate, Kth Smallest, and What Interviews Actually Test

A lot of candidates walk into BST questions thinking they're just binary tree questions with extra steps. They're not. The BST property is a constraint that changes everything about how you traverse and reason about the tree — and interviewers know exactly which candidates are exploiting that property versus treating the tree like a generic structure.

The property is simple: for any node, every value in its left subtree is strictly less than the node's value, and every value in its right subtree is strictly greater. No duplicates (unless the problem explicitly says otherwise). This one rule makes in-order traversal — left, root, right — produce values in sorted ascending order. That's the unlock for most BST problems.

In-order traversal of this tree gives: 1, 3, 4, 6, 7, 8, 10, 14 — sorted. Keep that in your head. It's the key to two of the three problems below.

Validate Binary Search Tree (LeetCode 98)

The naive approach everyone tries first: collect all values via in-order traversal into an array, then check if the array is strictly sorted. That works. It's O(n) time and O(n) space.

// Brute force — in-order collect then validate
// Time: O(n) — visit every node once
// Space: O(n) — store all node values
 
const isValidBST = (root) => {
  const values = [];
 
  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  };
 
  inorder(root);
 
  for (let i = 1; i < values.length; i++) {
    if (values[i] <= values[i - 1]) return false;
  }
 
  return true;
};

That's the solution you reach for when you know the property but haven't internalized it. The interviewer will accept it, maybe ask if you can do it without the array.

The optimized approach passes each node a valid range [min, max] as you recurse. At the root, the range is (-Infinity, +Infinity). Going left tightens the upper bound to the parent's value. Going right tightens the lower bound.

// Optimized — bounds propagation during DFS
// Time: O(n) — visit every node once
// Space: O(h) — recursion stack, h = tree height (log n balanced, n worst)
 
const isValidBST = (root) => {
  const validate = (node, min, max) => {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
 
    return validate(node.left, min, node.val) &&
           validate(node.right, node.val, max);
  };
 
  return validate(root, -Infinity, Infinity);
};

The bounds method is better not just because it skips the array, but because it can short-circuit early. The moment it finds an invalid node, it stops. The array approach always walks the whole tree.

One edge case worth mentioning: the problem uses [-2^31, 2^31 - 1] as the node value range, so you will see solutions that pass null as the initial bounds instead of ±Infinity. Those need an extra guard, because the comparisons above coerce: null becomes 0, so node.val <= min is -2 <= 0 — true — and a perfectly valid BST like [0, -2, 3] gets rejected. If you use null bounds, write the check as (min !== null && node.val <= min) || (max !== null && node.val >= max). Seeding with -Infinity and Infinity avoids the whole problem.

Kth Smallest Element in a BST (LeetCode 230)

If in-order gives you sorted order, finding the kth smallest is just "do an in-order traversal and stop at the kth node." The insight is stopping early instead of collecting everything.

Brute force first — collect all values, return index k-1:

// Brute force — collect in-order, index into result
// Time: O(n) — traverse full tree
// Space: O(n) — store all values
 
const kthSmallest = (root, k) => {
  const values = [];
 
  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  };
 
  inorder(root);
  return values[k - 1];
};

Now the optimization: keep a counter, stop the moment you've visited k nodes.

// Optimized — early-exit in-order traversal
// Time: O(h + k) — go to leftmost node (height h), then visit k nodes
// Space: O(h) — recursion stack depth
 
const kthSmallest = (root, k) => {
  let count = 0;
  let result = null;
 
  const inorder = (node) => {
    if (!node || result !== null) return; // early exit once found
 
    inorder(node.left);
 
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
 
    inorder(node.right);
  };
 
  inorder(root);
  return result;
};

The time complexity is O(h + k) where h is the height of the tree. You spend O(h) getting to the leftmost node (the smallest), then O(k) visiting nodes until you hit the target. For a balanced BST of n nodes, h = log n, so this can be significantly faster than O(n) when k is small.

BST Iterator (LeetCode 173)

This one trips people up because it looks like a design problem, not a traversal problem. You need to implement an iterator that yields values from the BST in ascending order, with next() and hasNext() methods. The constraint: O(h) space, where h is the tree height — not O(n).

The trick is simulating in-order traversal iteratively using an explicit stack. Instead of pushing all nodes at once, you lazily push only the path to the current leftmost unvisited node.

// BST Iterator — lazy iterative in-order traversal
// Time: O(1) amortized for next() — each node pushed/popped exactly once
// Space: O(h) — at most h nodes on stack at any time
 
class BSTIterator {
  constructor(root) {
    this.stack = [];
    this._pushLeft(root);
  }
 
  // Push the leftmost spine of the subtree rooted at node
  _pushLeft(node) {
    while (node) {
      this.stack.push(node);
      node = node.left;
    }
  }
 
  next() {
    const node = this.stack.pop();
    // If this node has a right child, push its leftmost spine
    this._pushLeft(node.right);
    return node.val;
  }
 
  hasNext() {
    return this.stack.length > 0;
  }
}

Why is next() O(1) amortized? Each node is pushed exactly once and popped exactly once across all next() calls. Spread over n calls, that's O(n) total work — O(1) per call on average. Individual calls might push a long spine, but those pushes were "paid for" in advance.

This pattern — controlling an in-order traversal with an explicit stack — shows up in other problems too. If you need to do "interleaved" traversal of two BSTs simultaneously, this is exactly how you'd do it.

The Insert and Delete Cases

Quick coverage since they show up in easier interview problems:

Insert is straightforward — follow the BST property to find where the new value belongs, then attach it as a leaf:

// BST Insert — recursive
// Time: O(h) — O(log n) balanced, O(n) worst case
// Space: O(h) — recursion stack
 
const insertIntoBST = (root, val) => {
  if (!root) return { val, left: null, right: null };
 
  if (val < root.val) {
    root.left = insertIntoBST(root.left, val);
  } else {
    root.right = insertIntoBST(root.right, val);
  }
 
  return root;
};

Delete (LeetCode 450) has three cases:

1. Node is a leaf — just remove it.
2. Node has one child — replace node with that child.
3. Node has two children — replace node's value with its in-order successor (leftmost node in right subtree), then delete that successor.

// BST Delete — handle all three cases
// Time: O(h) — finding node + finding successor
// Space: O(h) — recursion stack
 
const deleteNode = (root, key) => {
  if (!root) return null;
 
  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Found it. Handle the three cases.
    if (!root.left) return root.right;
    if (!root.right) return root.left;
 
    // Two children: find in-order successor (min of right subtree)
    let successor = root.right;
    while (successor.left) successor = successor.left;
 
    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val);
  }
 
  return root;
};

Interview Tips

Start by verifying the BST property. If the interviewer says "binary tree" not "binary search tree," don't assume sorted order. Ask explicitly. Candidates lose points for silently assuming a constraint that wasn't given.

In-order is your best friend. If a BST problem involves order statistics (kth smallest/largest, median, rank), your first thought should be in-order traversal. It's almost always the path to the optimal solution.

Know your complexities by height vs. n. BST operations are O(h) not O(log n). For a balanced tree, h = log n. For a degenerate tree (sorted input), h = n. If an interviewer asks "what's the worst case?" the answer involves unbalanced trees. Bonus points if you mention that self-balancing trees (AVL, Red-Black) guarantee O(log n).

The bounds trick generalizes. Validate BST uses min/max bounds. That same pattern — passing down constraints during recursion — appears in other tree problems. It's worth having as a mental template.

Watch for the iterator problem as a design follow-up. Combining BST traversal with the iterator pattern is a natural pairing — LeetCode 173 exists precisely because it is a common ask. Practice the explicit-stack version of in-order until it's automatic. It's the kind of thing that separates people who've internalized tree traversal from people who've just memorized it.