Trees & Binary Search Trees

A tree models hierarchy — a file system, the DOM, an org chart, a decision process. It is a set of nodes connected by edges with one root at the top and no cycles. Every node has one parent (except the root) and any number of children.

The binary tree — each node has at most two children (left and right) — is the most important variant because it maps so cleanly onto recursion: solve the left subtree, solve the right subtree, combine. Most tree problems are three lines of recursion once you see the structure.

Binary Search Tree — the ordering invariant

A BST adds one rule: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. That single invariant means each comparison discards an entire subtree — search, insert, and delete all follow one root-to-leaf path.

The cost is the height h. A balanced tree has h ≈ log n, giving O(log n) operations. But insert sorted data into a plain BST and it degenerates into a linked list with h = n — hence self-balancing trees.

The recursion template

Almost every binary-tree problem — height, sum, mirror, path checks — fits the same shape: handle the empty case, recurse both sides, combine.

function height(node) {
  if (!node) return 0                          // base case
  return 1 + Math.max(
    height(node.left),                         // solve left
    height(node.right),                        // solve right
  )                                            // combine
}

function insert(root, val) {
  if (!root) return { val, left: null, right: null }
  if (val < root.val) root.left = insert(root.left, val)
  else if (val > root.val) root.right = insert(root.right, val)
  return root
}