Binary Search Trees

A binary search tree (BST) is a binary tree that satisfies one extra rule — the BST invariant:

• Every key in a node’s left subtree is strictly less than the node’s key.
• Every key in a node’s right subtree is strictly greater than the node’s key.
• Both subtrees are themselves valid BSTs.

This invariant holds at every node, not just the root.

Verifying the Invariant

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

function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.val <= min || node.val >= max) return false;
  return isValidBST(node.left, min, node.val) &&
         isValidBST(node.right, node.val, max);
}

// Build a valid BST:   4
//                    /   \
//                   2     6
//                  / \   / \
//                 1   3 5   7
const root = new TreeNode(4,
  new TreeNode(2, new TreeNode(1), new TreeNode(3)),
  new TreeNode(6, new TreeNode(5), new TreeNode(7)),
);
console.log(isValidBST(root)); // true

Passing min and max bounds down the recursion is critical. Checking only the immediate parent would miss cases like a right subtree containing a node smaller than the root.

Inorder Traversal = Sorted Output

Because the invariant forces all smaller values left and all larger values right, an inorder traversal (left → root → right) always visits keys in ascending order.

function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.val);
  inorder(node.right, result);
  return result;
}

console.log(inorder(root)); // [1, 2, 3, 4, 5, 6, 7]

This is why “kth smallest element in BST” becomes: run inorder, return the kth element.

Searching a BST

The invariant lets each comparison eliminate an entire subtree:

function search(node, target) {
  if (!node) return null;
  if (target === node.val) return node;
  return target < node.val
    ? search(node.left, target)
    : search(node.right, target);
}

Each step discards half the remaining keys (if the tree is balanced), giving O(log n) search — the same as binary search on a sorted array.

The Degenerate BST Problem

Inserting keys in sorted order produces a degenerate BST that is effectively a linked list:

// Inserting 1, 2, 3, 4, 5 in order produces:
// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
// Height = n - 1  →  search is O(n), not O(log n).

This is the motivation for self-balancing trees (AVL, red-black) which maintain O(log n) height regardless of insertion order.

Up Next

Knowing the BST property is step one. The next lesson implements the three core mutation operations — insert, search, and the tricky three-case delete.