DAY 20 / 30 · WEEK 3

Binary Search Trees

Goal of the day

• Meet the BST invariant: for every single node, everything in its left subtree is smaller than it, and everything in its right subtree is larger — not just its immediate children, its entire subtree on each side.
• Implement insert (walk left/right by comparison until you find an empty spot) and search (the exact same left/right walk, stopping early on a match or a dead end) on the same TreeNode class Day 19 already introduced.
• Implement isValidBST correctly — and see exactly why checking only "left child < parent < right child" at each node is a trap that lets genuinely invalid trees slip through.
• Know the honest complexity: insert/search are O(h), where h is the tree's height — O(log n) only if the tree stays roughly balanced, and O(n) on a skewed tree. "BST operations are O(log n)" is an overclaim unless you say "for a balanced tree."

Concept

A binary search tree (BST) uses the exact same TreeNode class as Day 19 — val, left, right — and the exact same shape (at most two children per node). What changes is where a new value is allowed to go. Day 19's tree had no ordering rule at all — a new node could land "wherever there's room." A BST adds one rule and enforces it everywhere: at every node, every value in its left subtree must be smaller than it, and every value in its right subtree must be larger. That one rule is what makes insert and search fast — it turns "where do I look?" into a single comparison at each step instead of a full scan.

Think of a well-organized filing cabinet, or a paper phone book: entries are kept in sorted order specifically so you never have to scan the whole thing. Looking for "Mendez"? Open roughly to the middle — say you land on "K". "Mendez" comes after "K" alphabetically, so you already know the entire first half of the book (everything from "A" to "K") can't contain it — skip it, and only look to the right. That's exactly Day 12's binary search, applied to a tree instead of a sorted array: one comparison eliminates an entire subtree, not just one entry.

A BST bakes that same idea into its shape. Instead of a sorted array you binary search over with lo/hi/mid, the sort order lives in the tree's structure itself — "go left" or "go right" at each node is the narrowing step, and the empty spot where a walk runs out of tree is where a new value belongs.

Diagram: a valid BST and its invariant

Diagram: insert's walk — deciding left/right until an empty spot

Diagram: why "just check parent vs. child" validation is wrong

Interactive visualization: insert into a BST

Interactive visualization: search a BST

The code: insert, search, isValidBST

// Same TreeNode class as Day 19 — val, left, right. What's new today is the
// RULE every insert obeys: smaller goes left, larger goes right, at every node.
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function insert(root, val) {
  if (!root) return new TreeNode(val);    // empty spot found — this is where val belongs
  if (val < root.val) root.left = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  // val === root.val: already present — no duplicate inserted, tree unchanged
  return root;
}

function search(root, val) {
  if (!root) return false;                // fell off the tree — dead end, not found
  if (val === root.val) return true;      // match
  return val < root.val ? search(root.left, val) : search(root.right, val);
}

// The classic trap: checking only "left.val < node.val < right.val" at each node
// misses violations against a GRANDPARENT or higher ancestor. Thread a min/max
// bound down through the recursion instead — every node must fall strictly
// between the tightest bounds set by ALL of its ancestors, not just its parent.
function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;                 // an empty tree (or empty subtree) is valid
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

Line by line:

• TreeNode is unchanged from Day 19 — the BST invariant is a rule about where values are placed, not a new field on the node itself.
• insert recurses one comparison at a time: smaller goes left, larger goes right, and the base case if (!root) return new TreeNode(val) is exactly the empty spot the walk was looking for — that returned new node gets wired back in as the parent's .left or .right by the assignment one level up.
• search has the identical walk shape as insert, minus the wiring-in step — it's Day 12's binary search comparison (lo/hi/ mid) with the tree's own structure standing in for the sorted array.
• isValidBST is the one genuinely new idea: min/max start at ±Infinity and tighten by exactly one side on every recursive call — going left tightens max to the current node's value (nothing further left may exceed it), going right tightens min. That's what makes it check every ancestor, not just the immediate parent — by the time you reach node 6 in the trap diagram above, its inherited bound is (min=10, max=15), not just (−∞, 15), so 6 <= 10 correctly fails.

Dry run: insert(65) into the 7-node BST above

Three nodes deep, two real comparisons — the walk always terminates the instant it steps toward a null child, which is exactly where the new node belongs.

Complexity

h = the tree's height, n = total nodes. O(h) is not automatically O(log n). On a balanced tree, h ≈ log n, and insert/search really do run in logarithmic time — that's the whole appeal of a BST. But nothing about a plain BST keeps it balanced: insert 1, 2, 3, 4, 5 in that exact order and every new value is always larger than everything already in the tree, so each one becomes the previous node's right child. The result is a straight rightward chain — height n, no branching at all — and insert/search degrade to O(n), the same cost as scanning a linked list. Say "O(log n) for a balanced BST," never "O(log n) BST operations" unqualified.

Interview corner

• Why is checking only "left child < parent < right child" at each node not enough to validate a BST? Because the BST invariant is about a node's entire subtree on each side, not just its immediate children. A node can be perfectly ordered relative to its own parent while still violating the invariant relative to a grandparent or higher ancestor — see the diagram above, where node 6 is fine next to its parent 15 but invalid relative to root 10.
  ⚠ Trap: this exact local-only check is the single most common wrong isValidBST submission — it passes small hand-checked examples (parent/child pairs all look fine!) and fails the moment a grandparent-level violation is hidden three levels down.
• How does threading min/max bounds through the recursion fix it? Every recursive call carries the tightest lower and upper bound inherited from every ancestor so far, not just the direct parent. Going left tightens the upper bound to the current node's value; going right tightens the lower bound. By the time you reach any node, its bounds already encode every ancestor's constraint, so one comparison (min < node.val < max) is enough to catch a violation from any depth.
• Are BST insert/search really O(log n)? Only if the tree is reasonably balanced. The honest complexity is O(h), h = height — O(log n) when h stays proportional to log n, but O(n) on a skewed tree (e.g. inserting already-sorted data, which produces a straight chain).
  ↳ Common follow-up: "How would you keep it balanced?" — self-balancing variants (AVL trees, red-black trees) add rotation rules after insert/delete specifically to bound the height at O(log n) no matter the insert order; a plain BST as shown today has no such guarantee.
• Why does insert silently do nothing when val already exists? The template shown treats a BST as a set of distinct values — the val === root.val case falls through both comparisons and the function just returns the unchanged subtree. Some variants intentionally allow duplicates (commonly by routing them to the right, "duplicates go right" as a convention) — always confirm with the interviewer which behavior is expected before assuming one.
• What's the very first edge case to say out loud for any of these three functions? The empty tree (root === null). insert must create the very first node instead of dereferencing null.val; search must return false instead of crashing; isValidBST must return true (an empty tree trivially satisfies the invariant) — the same "guard null before touching .val" habit from Day 19 applies to every one of today's three functions.

How to talk through it out loud: name the invariant before writing a line — "at every node, left subtree is smaller, right subtree is larger" — then narrate each walk as a single comparison per step: "is my target smaller or larger than the current node? that tells me the only subtree worth looking in." For isValidBST specifically, say the trap out loud before coding it: "checking just the immediate parent isn't enough — I need to carry a min and max bound down from every ancestor." Interviewers on this topic are listening for whether you state the invariant precisely (not "sorted," but "left subtree fully smaller, right subtree fully larger, at every node") and whether you qualify O(log n) with "if balanced" instead of asserting it unconditionally.

Practice problems

function searchBST(root, val) {
  if (!root) return null;
  if (root.val === val) return root;
  return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

function insertIntoBST(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insertIntoBST(root.left, val);
  else root.right = insertIntoBST(root.right, val);
  return root;
}

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

Quiz