Trees & Binary Search Trees

The big idea

A family tree or a company org chart: one person at the top, each person has zero or more people below them, and nobody reports to two bosses. That's a tree.

You already use trees daily: folders on your computer, the HTML DOM, JSON objects, React component trees, and database indexes (B-trees).

Tree vocabulary

Tree vocabulary: root, parent, child, leaf, depth and height

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

Trees love recursion

Every subtree is itself a tree. So most tree problems follow the same shape: solve for the left subtree, solve for the right subtree, combine.

// Height of a tree
function height(node) {
  if (node === null) return 0;                              // base case: empty tree
  return 1 + Math.max(height(node.left), height(node.right)); // combine
}

// Count nodes
const count = (node) => (node ? 1 + count(node.left) + count(node.right) : 0);

The four traversals

For this tree:

The three depth-first traversals are the same function with one line moved:

function preorder(node, result = []) {
  if (node === null) return result;
  result.push(node.value);        // root first
  preorder(node.left, result);
  preorder(node.right, result);
  return result;
}

function inorder(node, result = []) {
  if (node === null) return result;
  inorder(node.left, result);
  result.push(node.value);        // root in the middle
  inorder(node.right, result);
  return result;
}

function postorder(node, result = []) {
  if (node === null) return result;
  postorder(node.left, result);
  postorder(node.right, result);
  result.push(node.value);        // root last
  return result;
}

Level-order uses a queue:

function levelOrder(root) {
  if (!root) return [];
  const levels = [];
  let queue = [root];
  while (queue.length) {
    levels.push(queue.map((n) => n.value));
    queue = queue.flatMap((n) => [n.left, n.right].filter(Boolean));
  }
  return levels; // [[1], [2, 3], [4, 5]]
}

💡 Memory trick: "pre", "in" and "post" describe when you visit the root: before, in between, or after its children.

Binary Search Tree (BST)

A BST adds one rule: for every node, everything on the left is smaller and everything on the right is bigger.

To find 7: 7 < 8 → go left · 7 > 3 → go right · 7 > 6 → go right · found! Each step throws away half the tree, just like binary search.

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

function insert(node, value) {
  if (!node) return new TreeNode(value);
  if (value < node.value) node.left = insert(node.left, value);
  else node.right = insert(node.right, value);
  return node;
}

Balanced vs unbalanced

Self-balancing trees (AVL, Red-Black) rotate nodes automatically to stay balanced. Databases use B-trees, wide trees with many keys per node, so a lookup touches only 3–4 disk pages even with millions of rows.

Classic interview problems

// Is this a valid BST? Every node must fit within a (min, max) range.
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.value <= min || node.value >= max) return false;
  return isValidBST(node.left, min, node.value) && isValidBST(node.right, node.value, max);
}

// Invert (mirror) a binary tree
function invert(node) {
  if (!node) return null;
  [node.left, node.right] = [invert(node.right), invert(node.left)];
  return node;
}

Key takeaways

• Trees model hierarchies: folders, DOM, org charts, JSON.
• Most tree problems are recursion: solve left, solve right, combine.
• Four traversals: pre-, in-, post-order (DFS) and level-order (BFS with a queue).
• In-order traversal of a BST gives sorted values.
• BST search is O(log n) only when the tree is balanced.