Balanced Binary Tree

Explanation

An ordinary binary search tree (BST) degenerates when elements are inserted in sorted order: 1, 2, 3, 4, 5 creates a chain of right children (effectively a linked list) with height O(n). Every search, insert, and delete then takes O(n) instead of O(log n). Balanced binary trees prevent this by automatically restructuring themselves to maintain a height of O(log n). The two most common self-balancing BST implementations are AVL trees and Red-Black trees. AVL trees maintain the strict balance property that the heights of the two subtrees of any node differ by at most 1. They use rotations (single and double) to restore balance after insertions and deletions. Red-Black trees use a coloring scheme (each node is red or black) with five invariants to ensure the tree never has a path from root to leaf more than twice as long as any other — equivalent to O(log n) height. Red-Black trees are slightly less balanced than AVL trees but require fewer rotations on insert/delete, making them faster for write-heavy workloads. Java's TreeMap and TreeSet, C++'s std::map and std::set, and Python's sortedcontainers all use Red-Black trees or equivalent structures. B-trees (generalizations of balanced BSTs where each node can have many children) are used in database indexes and file systems because they minimize disk I/O by maximizing the branching factor, keeping the tree extremely shallow. When your database uses an index on a column, it's almost certainly a B-tree or B+ tree internally.

Code Example

// Height-balance check for a binary tree (interview problem)
// Returns height if balanced, -1 if not

function checkHeight(node) {
  if (!node) return 0;

  const left = checkHeight(node.left);
  if (left === -1) return -1; // left subtree unbalanced

  const right = checkHeight(node.right);
  if (right === -1) return -1; // right subtree unbalanced

  if (Math.abs(left - right) > 1) return -1; // this node unbalanced

  return 1 + Math.max(left, right); // return height
}

function isBalanced(root) {
  return checkHeight(root) !== -1;
}

// Note: full self-balancing BST implementations (AVL, Red-Black)
// are complex — in production, use your language's built-in
// sorted map/set which handles balancing internally.

Why It Matters for Engineers

Database performance fundamentally depends on balanced tree structures. When you add an index to a database column, you're telling the database to build a balanced B-tree over that column's values, turning O(n) table scans into O(log n) index lookups. Understanding why balanced trees are faster than unbalanced ones — and why unindexed queries are slow — is core database knowledge. In interviews, "is this tree balanced?" is a common question that requires understanding the balance definition and writing a recursive height-checking algorithm. More broadly, balanced trees illustrate a key engineering principle: the worst-case behavior of a system (the degenerate BST) can be orders of magnitude worse than the average case, and engineering effort to bound worst-case behavior is worth it.