BST Operations

The three operations that define a BST’s usefulness — insert, search, and delete — all exploit the same invariant: go left if smaller, go right if larger. Insert and search are straightforward; delete requires care because removing a node must preserve the invariant for the entire subtree.

Insert

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

function insert(root, val) {
  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);
  }
  // duplicate values are ignored here; adjust as needed
  return root;
}

Each recursive call moves one level deeper. The new node always lands at a null position, so no existing node needs to move.

Search

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

Returns the matching node or null. Each comparison eliminates one subtree.

Delete — Three Cases

Deletion is the hardest BST operation because the deleted node might have children that must be re-attached.

Case 1: Leaf node — simply remove it (return null to the parent).

Case 2: One child — replace the node with its only child.

Case 3: Two children — find the in-order successor (the smallest node in the right subtree), copy its value into the current node, then delete the successor from the right subtree. The successor has at most one child (no left child), so its own deletion is always Case 1 or Case 2.

function findMin(node) {
  while (node.left) node = node.left;
  return node;
}

function deleteNode(root, val) {
  if (!root) return null;

  if (val < root.val) {
    root.left = deleteNode(root.left, val);
  } else if (val > root.val) {
    root.right = deleteNode(root.right, val);
  } else {
    // Found the node to delete
    if (!root.left) return root.right;   // Case 1 or 2 (no left child)
    if (!root.right) return root.left;   // Case 2 (no right child)

    // Case 3: two children — replace with in-order successor
    const successor = findMin(root.right);
    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val);
  }
  return root;
}

Why the Successor Preserves the Invariant

The in-order successor is the smallest key that is still larger than the deleted node. Placing it at the deleted position means:

• All left-subtree values remain smaller (they were smaller than the deleted node, which was smaller than the successor).
• All right-subtree values remain larger (the successor was the minimum of the right subtree).

Complexity

All three operations follow the same root-to-leaf path, so their complexity equals the tree height — O(log n) when balanced, O(n) in the worst case.

Up Next

Understanding tree height precisely leads to algorithms that compute depth, height, and diameter in a single bottom-up pass.