Binary Search Trees

The BST property

A Binary Search Tree is a binary tree with one invariant: for every node, all values in its left subtree are strictly less than the node’s value, and all values in its right subtree are strictly greater.

      5
     / \
    3   7
   / \ / \
  2  4 6  8

This isn’t just about direct children — it applies to the entire subtree. 2, 3, 4 are all less than 5. 6, 7, 8 are all greater.

Search

Because of the BST property, at each node we can eliminate half the tree:

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

Each comparison eliminates one subtree. Time: O(h) where h is height. For a balanced BST, h = O(log n). For a degenerate BST (sorted insertion), h = O(n).

Insert

Find the correct position, insert as a leaf:

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val)
  if (val < root.val) root.left  = insert(root.left,  val)
  else if (val > root.val) root.right = insert(root.right, val)
  // val === root.val: duplicate — do nothing (or handle per spec)
  return root
}

Validate BST

The most common mistake: only checking direct children, not the full subtree constraint.

Wrong:

function isValidBST_WRONG(root: TreeNode | null): boolean {
  if (!root) return true
  if (root.left && root.left.val >= root.val) return false
  if (root.right && root.right.val <= root.val) return false
  return isValidBST_WRONG(root.left) && isValidBST_WRONG(root.right)
}
// Fails on: [5,4,6,null,null,3,7] — node 3 is in the right subtree of 5 but < 5

Correct: pass min/max bounds down the recursion:

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

When we go left, the current node value becomes the new max (everything in the left subtree must be less than current). When we go right, current value becomes the new min.

In-order gives sorted output

In-order traversal of a BST (left → root → right) visits nodes in ascending order. This is a key property:

// Kth smallest element in BST
function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0, result = 0
  function inorder(node: TreeNode | null): void {
    if (!node) return
    inorder(node.left)
    count++
    if (count === k) { result = node.val; return }
    inorder(node.right)
  }
  inorder(root)
  return result
}

Delete

Three cases:

1. Leaf node — just remove it
2. One child — replace node with its child
3. Two children — replace node’s value with its in-order successor (smallest node in right subtree), then delete the successor

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  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 node to delete
    if (!root.left)  return root.right  // case 1 & 2
    if (!root.right) return root.left   // case 2

    // Case 3: two children — find in-order successor (leftmost of right subtree)
    let successor = root.right
    while (successor.left) successor = successor.left
    root.val   = successor.val               // replace value
    root.right = deleteNode(root.right, root.val)  // delete successor
  }
  return root
}

BST vs Hashmap

Both give you O(1) average / O(log n) worst case for key lookup. Use a BST when you need ordered operations that a hashmap can’t do efficiently:

In JavaScript, there’s no built-in BST. Use a sorted array with binary search for read-heavy ordered workloads, or a library (like @js-sdsl/ordered-map) for production.

Range sum of BST

Sum all node values between low and high (inclusive):

function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
  if (!root) return 0
  let sum = 0
  if (root.val >= low && root.val <= high) sum += root.val
  if (root.val > low)  sum += rangeSumBST(root.left,  low, high)  // left subtree might have values ≥ low
  if (root.val < high) sum += rangeSumBST(root.right, low, high)  // right subtree might have values ≤ high
  return sum
}

The BST property lets us prune: if root.val <= low, the entire left subtree is below range — skip it. If root.val >= high, skip the right subtree. This gives O(log n + output) instead of O(n).

Complexity

Self-balancing trees (AVL, Red-Black) maintain O(log n) worst case by rebalancing on insert/delete. JavaScript has no built-in balanced BST, but the interview world mostly tests vanilla BST logic.