Binary search tree

Overview

A binary search tree (BST) is a binary tree with an ordering rule: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That rule lets search, insert, and delete discard one subtree at each step, just like binary search on a sorted array.

Operations cost O(h), where h is the height. A balanced BST has h = O(log n), but inserting sorted data into a plain BST produces a chain with h = n. That is why production systems use self-balancing trees (see Balanced search trees).

When to use it

• You need sorted data with fast inserts and deletes (arrays make inserts O(n)).
• Floor, ceiling, predecessor, successor, or range queries.
• The problem gives a BST and asks to exploit ordering.
• Maintaining an ordered set or map (Java TreeMap / TreeSet).

Problem patterns it solves

Where it is used in real software

Key terms

BST property

left subtree < node < right subtree, for every node.

Inorder successor

The next larger value: the leftmost node of the right subtree.

Floor / ceiling

Largest value <= x / smallest value >= x.

Degenerate tree

A BST shaped like a linked list, with O(n) operations.

Deleting a node

1. 1
   Find the node

   Go left if key < node.val, right if larger.

2. 2
   Case 1: leaf

   Remove it by returning null to the parent.

3. 3
   Case 2: one child

   Replace the node with its only child.

4. 4
   Case 3: two children

   Find the inorder successor (smallest in the right subtree), copy its value into the node, then delete the successor from the right subtree.

Search for 6 and insert 5

BST: 8 (left 3, right 10); 3 (left 1, right 6); 6 (left 4, right 7)

Each step goes down one level, so the cost is the height of the tree. New values are always inserted as leaves.

Implementation

1function searchBST(root, val) {2  let node = root;3  while (node && node.val !== val) node = val < node.val ? node.left : node.right;4  return node;5}6 7function insertIntoBST(root, val) {8  if (!root) return new TreeNode(val);9  if (val < root.val) root.left = insertIntoBST(root.left, val);10  else root.right = insertIntoBST(root.right, val);11  return root;12}13 14function deleteNode(root, key) {15  if (!root) return null;16  if (key < root.val) root.left = deleteNode(root.left, key);17  else if (key > root.val) root.right = deleteNode(root.right, key);18  else {19    if (!root.left) return root.right;20    if (!root.right) return root.left;21    let successor = root.right;22    while (successor.left) successor = successor.left;23    root.val = successor.val;24    root.right = deleteNode(root.right, successor.val);25  }26  return root;27}28 29// Validate with inherited bounds, not just parent comparison30function isValidBST(node, low = -Infinity, high = Infinity) {31  if (!node) return true;32  if (node.val <= low || node.val >= high) return false;33  return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, high);34}35 36function sortedArrayToBST(nums, lo = 0, hi = nums.length - 1) {37  if (lo > hi) return null;38  const mid = (lo + hi) >> 1;39  return new TreeNode(nums[mid], sortedArrayToBST(nums, lo, mid - 1), sortedArrayToBST(nums, mid + 1, hi));40}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Validating only against the parent.

  Fix: A node deep in the left subtree must also be smaller than every ancestor it is left of. Pass bounds down.

• Duplicates.

  Fix: Decide a rule (go right, or keep a count) and apply it consistently.

• Integer bounds in Java validation.

  Fix: Use Long or nullable Integer bounds; node values can equal Integer.MIN_VALUE.

Interview questions

Practice problems