Binary Search Trees

A BST is not just “a tree with sorted children.”
A BST is a recursive ordering contract on full subtrees.

If you preserve that contract, search/update/range operations become logarithmic on balanced trees.

BST Invariant (Precise Form)

For every node x:

• all keys in x.left are < x.val
• all keys in x.right are > x.val

This is a global subtree property, not a direct-child check.

Node Model

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

Duplicate policy must be defined upfront:

• strict BST: disallow duplicates
• duplicate-on-right convention
• duplicate count per node

Never mix policies.

Complexity Depends on Height

All core BST operations are O(h), where h is tree height.

• balanced tree: h = O(log n)
• skewed tree (sorted inserts): h = O(n)

This is why balancing strategy matters in production.

Search (Recursive + Iterative)

function searchBST(root: TreeNode | null, target: number): TreeNode | null {
  if (root === null || root.val === target) return root
  if (target < root.val) return searchBST(root.left, target)
  return searchBST(root.right, target)
}

function searchBSTIter(root: TreeNode | null, target: number): TreeNode | null {
  let curr = root
  while (curr !== null) {
    if (curr.val === target) return curr
    curr = target < curr.val ? curr.left : curr.right
  }
  return null
}

Iterative avoids recursion depth concerns.

Insert

function insertBST(root: TreeNode | null, val: number): TreeNode {
  if (root === null) return new TreeNode(val)

  if (val < root.val) root.left = insertBST(root.left, val)
  else if (val > root.val) root.right = insertBST(root.right, val)
  // equal case depends on duplicate policy; here we ignore

  return root
}

Invariant reasoning:

• recursive insert only mutates one root-to-leaf path
• untouched subtrees keep invariant

Validate BST (Correct Way)

Wrong idea (direct children only)

Fails on cases like [5,4,6,null,null,3,7] because 3 violates ancestor bound.

Correct: propagate min/max bounds

function isValidBST(root: TreeNode | null): boolean {
  function dfs(node: TreeNode | null, min: number, max: number): boolean {
    if (node === null) return true
    if (node.val <= min || node.val >= max) return false
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max)
  }
  return dfs(root, -Infinity, Infinity)
}

Equivalent approach: in-order traversal must be strictly increasing.

In-Order Property and Kth Smallest

In-order traversal (left -> root -> right) on BST yields sorted sequence.

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = []
  let curr = root
  let seen = 0

  while (stack.length > 0 || curr !== null) {
    while (curr !== null) {
      stack.push(curr)
      curr = curr.left
    }
    curr = stack.pop()!
    seen++
    if (seen === k) return curr.val
    curr = curr.right
  }
  return -1
}

Iterative in-order is a common interview expectation.

Delete Node (Most Important BST Mutation)

Cases:

1. leaf -> remove directly
2. one child -> replace with child
3. two children -> replace value with inorder successor (or predecessor), then delete that node

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null

  if (key < root.val) {
    root.left = deleteNode(root.left, key)
    return root
  }
  if (key > root.val) {
    root.right = deleteNode(root.right, key)
    return root
  }

  // key == root.val
  if (root.left === null) return root.right
  if (root.right === null) return root.left

  // two children: find successor (min of right subtree)
  let succ = root.right
  while (succ.left !== null) succ = succ.left

  root.val = succ.val
  root.right = deleteNode(root.right, succ.val)
  return root
}

Why successor deletion works:

• successor has no left child
• recursive delete is simpler in right subtree
• ordering invariant preserved

Floor, Ceil, Predecessor, Successor

Ordered queries are where BST beats hashmap.

Floor (largest <= x)

function floorBST(root: TreeNode | null, x: number): number | null {
  let curr = root
  let ans: number | null = null
  while (curr !== null) {
    if (curr.val === x) return x
    if (curr.val < x) {
      ans = curr.val
      curr = curr.right
    } else {
      curr = curr.left
    }
  }
  return ans
}

Ceil (smallest >= x)

function ceilBST(root: TreeNode | null, x: number): number | null {
  let curr = root
  let ans: number | null = null
  while (curr !== null) {
    if (curr.val === x) return x
    if (curr.val > x) {
      ans = curr.val
      curr = curr.left
    } else {
      curr = curr.right
    }
  }
  return ans
}

Successor and predecessor

• successor = next larger key
• predecessor = next smaller key

Can be found via path traversal in O(h), optionally using subtree min/max if node found.

Range Query / Range Sum with Pruning

function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
  if (root === null) return 0
  if (root.val < low) return rangeSumBST(root.right, low, high)
  if (root.val > high) return rangeSumBST(root.left, low, high)
  return (
    root.val +
    rangeSumBST(root.left, low, high) +
    rangeSumBST(root.right, low, high)
  )
}

Pruning logic:

• if root too small, entire left subtree too small
• if root too large, entire right subtree too large

BST Iterator (In-Order Stream)

Useful for lazy traversal and interview design questions.

class BSTIterator {
  private stack: TreeNode[] = []

  constructor(root: TreeNode | null) {
    this.pushLeft(root)
  }

  private pushLeft(node: TreeNode | null): void {
    let curr = node
    while (curr !== null) {
      this.stack.push(curr)
      curr = curr.left
    }
  }

  next(): number {
    const node = this.stack.pop()!
    this.pushLeft(node.right)
    return node.val
  }

  hasNext(): boolean {
    return this.stack.length > 0
  }
}

Amortized O(1) per next, O(h) memory.

BST vs HashMap vs Sorted Array

Read-heavy static sets often prefer sorted arrays. Dynamic ordered sets prefer balanced BST structures.

Degeneration and Self-Balancing Trees

Plain BST can degrade to linked-list shape.

Self-balancing trees keep height O(log n):

• AVL
• Red-Black
• Treap
• Splay (amortized properties)

In JavaScript there is no built-in tree map/set, so production code uses libraries or alternative data structures.

Augmented BSTs (Advanced)

Attach metadata per node:

• subtree size -> kth smallest in O(log n)
• subtree sum -> range-sum style queries
• min gap, max endpoint, etc.

Rule: after any insertion/deletion, recompute augmented fields on unwind.

Common Bugs Checklist

1. Validate BST using only child checks
2. Forget duplicate policy and produce inconsistent tree
3. Delete case with two children but do not remove successor node
4. Wrong strictness (< vs <=) causing duplicate drift
5. Null dereference in iterative traversals
6. Assuming O(log n) without discussing skewed worst-case

Interview Communication Script

Say:

1. “All operations are O(h), where h is tree height.”
2. “I preserve subtree ordering invariant at each mutation.”
3. “For delete with two children, I swap with successor then delete successor.”

This signals full understanding, not memorized snippets.

Problem Ladder

Easy

• Search in BST
• Insert into BST
• Range Sum of BST

Medium

• Validate BST
• Kth Smallest in BST
• Delete Node in BST
• Inorder Successor in BST

Hard / high-signal

• Recover Binary Search Tree
• Serialize and Deserialize BST
• Validate Preorder Traversal of a BST
• Design BST iterator and augmented operations

Complexity Summary

Space:

• recursion depth O(h)
• iterative traversal stack O(h)

Final Takeaway

BST mastery is invariant mastery:

1. preserve recursive ordering contract,
2. reason in height h,
3. handle delete cases precisely,
4. exploit order-aware operations (floor/ceil/range).

Do that and BSTs become one of the cleanest ordered-data tools in your problem-solving toolkit.