Trees

How It Works

A tree is a hierarchical structure made of nodes, where each node holds a value and references to its children, and exactly one path connects the root to any other node (no cycles). It's a generalization of a linked list where each node can branch into multiple children instead of just one next. Trees model anything with natural hierarchy: the DOM, file systems, org charts, ASTs from parsing code, and decision structures.

A binary tree restricts each node to at most two children (left and right). A binary search tree (BST) adds an ordering invariant: everything in the left subtree is smaller than the node, everything in the right subtree is larger. That invariant is what makes search, insert, and delete average O(log n): each comparison eliminates roughly half the remaining nodes, the same idea as binary search on a sorted array. But a BST isn't guaranteed to be balanced; a degenerate BST built from already-sorted input degrades into a linked list, making all operations O(n). Self-balancing variants (AVL, red-black trees) exist specifically to prevent that worst case, though you rarely need to implement one from scratch in an interview.

Traversal is always O(n) since you must visit every node at least once. The three depth-first orders (preorder: node, left, right; inorder: left, node, right; postorder: left, right, node) and breadth-first level-order traversal (using a queue) are the standard building blocks almost every tree problem is composed from.

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

// O(n): visit every node, left subtree fully before right
function inorderTraversal(root) {
  const result = [];
  function visit(node) {
    if (!node) return;
    visit(node.left);
    result.push(node.value);
    visit(node.right);
  }
  visit(root);
  return result;
}

// O(h) average / O(n) worst-case: h is tree height
function insertIntoBST(root, value) {
  if (!root) return new TreeNode(value);
  if (value < root.value) {
    root.left = insertIntoBST(root.left, value);
  } else {
    root.right = insertIntoBST(root.right, value);
  }
  return root;
}

// Iterative level-order (BFS) traversal using a queue
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

Common Mistakes

• Assuming a BST is balanced: quoting O(log n) search without checking whether the input could produce a degenerate, list-like tree (e.g., inserting already-sorted values).
• Confusing traversal orders: mixing up preorder/inorder/postorder, especially when a problem depends on a specific one (inorder on a BST yields sorted output, which is a common trick).
• Forgetting the null/leaf base case in recursion: recursive tree functions need an explicit if (!node) return ... or they'll throw on leaves.
• Not tracking parent pointers when needed: some problems (like deletion or finding a successor) require walking back up, which a plain left/right node can't do unless you track parents explicitly or pass them down.
• Off-by-one in height/depth calculations: disagreeing on whether a single-node tree has height 0 or 1, which throws off balance checks and recursive base cases.

Pattern Summary

Reach for a tree whenever the data is naturally hierarchical or you need ordered, log-time search with the added benefit of sorted-order traversal: BST validation, lowest-common-ancestor, and serialize/deserialize problems all hinge on recursive divide-and-conquer over left/right subtrees. The edge it gives you in interviews is that most tree problems decompose cleanly into "solve for left subtree, solve for right subtree, combine," which maps directly onto recursion.