DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 7 of 16 · ~4 min

Trees

Alphabetized for fast browsing, the catalog itself is a binary search tree. Trees are recursive as a matter of definition — a node is just a value plus two smaller trees hanging off it — so code that walks one tends to write itself once you stop overthinking node.left and node.right and just ask each of them to handle their own half:

class CatalogNode {
  constructor(course, left = null, right = null) {
    this.course = course;      // { code, title, credits, ... }
    this.left = left;
    this.right = right;
  }
}

function preorder(node, out = []) {
  if (!node) return out;                  // an empty subtree adds nothing
  out.push(node.course.code);             // visit the ROOT first
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}

function inorder(node, out = []) {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.course.code);             // the root falls BETWEEN its two subtrees
  inorder(node.right, out);
  return out;
}

function postorder(node, out = []) {
  if (!node) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.course.code);             // the root comes LAST
  return out;
}

Three orders, three different jobs the planner actually has. Inorder on a BST comes out fully alphabetical — a direct consequence of how the tree was built, and the entire reason "browse everything starting with CS" or "list courses alphabetically" needs no separate sort step. Postorder fits the accreditation report's "total credit hours per catalog branch," since a parent's total can't be summed until both children's totals already exist. Preorder fits the nightly backup job, since a root-first dump can be replayed top to bottom to rebuild the exact same shape.

Something the pattern list above leaves out

Here's a question worth having an answer ready for, because a thorough interviewer asks it right after your clean BST lookup: what guarantees O(log n) search actually rests on the tree staying roughly balanced? Insert course codes in already-sorted order with no rebalancing and the "tree" flattens into a line — every node with exactly one child, lookup degraded to a linear scan, all the bookkeeping overhead of a tree buying none of its benefit. That's not a contrived edge case; a batch import that happens to insert codes alphabetically produces exactly this. Real systems reach for a self-balancing structure — an AVL tree, a red-black tree, the kind backing most languages' ordered map types — specifically to keep height at O(log n) regardless of insertion order. It's a fair thing for an interviewer to expect you to name, even without asking you to build one.

And since the call stack counts as memory (the Big-O chapter's closing note), recursive traversal spends O(h) stack space, h being the tree's height — O(log n) balanced, O(n) in the flattened worst case above. That's a real cost, not a matter of taste between recursion and an explicit stack.

Level-order traversal (BFS)

The catalog browser's interface doesn't want the whole alphabet dumped at once — it wants one level revealed at a time as a student clicks deeper:

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];               // a QUEUE, not a stack, is what makes this breadth-first

  while (queue.length) {
    const levelSize = queue.length;   // how many nodes belong to the CURRENT level
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();     // take from the front
      level.push(node.course.code);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

One honest wrinkle worth flagging: Array.prototype.shift() isn't actually O(1) in JavaScript. Pulling the front element off means every remaining element has to slide down one slot, an O(n) operation each call — so this exact code quietly runs O(n²) on a wide tree, despite the traversal it's implementing being O(n) in concept. Swap the array for a real deque, or keep a pointer that advances through the array instead of shrinking it, and the constant-factor cost disappears. What's worth actually remembering is the pattern underneath, not the array's quirk: measure the level before touching it, drain precisely that many nodes, queue up whatever they hand off to the next level. That move reappears unchanged the day "process this level by level" shows up on a graph rather than a tree.

Reach for recursive DFS when a problem is shaped like a single descent from top to bottom, or when it splits cleanly into "handle the left half, handle the right half, combine the two." Reach for BFS instead the instant the question cares about how many layers deep something is, or about the shortest route through a structure with no weights on its edges — it physically cannot touch anything two steps away before it's touched everything one step away.

Trees and Depth-First Search on Code Lab cover both halves.