What is a binary search tree?

The ordering property lets you discard half the tree at each step, similar to binary search on an array. The catch is that the bound depends on height. A balanced BST has h = O(log n); a BST built from sorted input becomes a linked list with h = O(n).

function search(node, target) {
  while (node !== null) {
    if (node.value === target) return node;
    node = target < node.value ? node.left : node.right;
  }
  return null;
}

function insert(node, value) {
  if (node === null) return { value, left: null, right: null };
  if (value < node.value) node.left = insert(node.left, value);
  else if (value > node.value) node.right = insert(node.right, value);
  return node;
}

Why balance matters

• A balanced tree gives O(log n) search and insertion
• Sorted insertion order creates a skewed tree with O(n) operations
• Self-balancing trees such as AVL and red-black trees maintain the bound
• Inorder traversal of any valid BST returns sorted values
• Deletion has three cases: leaf, one child and two children

For the two-child deletion case, replace the node with its inorder successor, the smallest value in the right subtree, then delete that successor. This preserves the ordering property without restructuring the whole tree.