Trees and Graphs Basics

Trees and graphs model relationships: hierarchies, networks, dependencies. Nearly every question about them reduces to one of two traversals — BFS or DFS — so this page focuses on getting those two cold.

Trees

A tree is nodes connected by edges, with one root and no cycles. A binary tree limits each node to two children:

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

BFS — level by level

Breadth-first search visits the tree one level at a time, using a queue. Use it when the question mentions levels, or when you want the shortest path from the root:

function levelOrder(root) {
  if (root === null) 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;
}

console.log(levelOrder(root)); // [1, 2, 3, 4, 5, 6]

DFS — go deep first

Depth-first search follows one branch to the bottom before backtracking. The three classic orders differ only in when they visit the current node relative to its children:

function inorder(node, out = []) {
  if (node === null) return out;
  inorder(node.left, out);
  out.push(node.value);
  inorder(node.right, out);
  return out;
}

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

console.log(inorder(root)); // [4, 2, 5, 1, 3, 6]
console.log(preorder(root)); // [1, 2, 4, 5, 3, 6]

Both traversals visit every node once: O(n) time. Space is O(h) for DFS — h being the tree height, from the recursion stack — and up to O(n) for BFS's queue on a wide tree.

Most tree questions are a traversal plus a twist. Height, for instance, is DFS where each node returns one plus the taller subtree:

function height(node) {
  if (node === null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

console.log(height(root)); // 3

Binary search trees

A BST keeps everything in the left subtree smaller than the node and everything in the right subtree larger. That invariant turns search into a guided walk — at every node you discard half the remaining tree:

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

On a balanced BST that is O(log n); if the tree degrades into a chain, it is O(n). Production systems use self-balancing variants — the same idea backs database indexes. A useful fact for interviews: inorder traversal of a BST yields its values in sorted order.

Graphs

A graph is nodes plus edges, with no root and possibly cycles. The standard representation in JavaScript is an adjacency list — a Map from each node to its neighbors:

const network = new Map([
  ["Rizwan", ["Hafsa", "Ibrahim"]],
  ["Hafsa", ["Rizwan", "Ayesha"]],
  ["Ibrahim", ["Rizwan", "Ayesha"]],
  ["Ayesha", ["Hafsa", "Ibrahim", "Zakariya"]],
  ["Zakariya", ["Ayesha"]],
]);

The two traversals carry over, with one addition: graphs can contain cycles, so you must track visited nodes or you will loop forever.

Graph BFS — shortest path in hops

BFS explores in rings of increasing distance, so the first time you reach a node is via a shortest path:

function shortestHops(graph, start, target) {
  const visited = new Set([start]);
  const queue = [[start, 0]];
  let head = 0;

  while (head < queue.length) {
    const [node, distance] = queue[head++];
    if (node === target) return distance;

    for (const neighbor of graph.get(node)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1]);
      }
    }
  }
  return -1;
}

console.log(shortestHops(network, "Rizwan", "Zakariya")); // 3

Rizwan reaches Zakariya in three hops — through Hafsa or Ibrahim, then Ayesha. This only works for unweighted graphs; weighted shortest paths need Dijkstra's algorithm.

Graph DFS — reachability and connectivity

DFS answers "what can I reach from here" — connected components, cycle detection, dependency resolution:

function reachable(graph, start) {
  const visited = new Set();

  function explore(node) {
    visited.add(node);
    for (const neighbor of graph.get(node)) {
      if (!visited.has(neighbor)) explore(neighbor);
    }
  }

  explore(start);
  return visited;
}

console.log([...reachable(network, "Zakariya")]);
// ["Zakariya", "Ayesha", "Hafsa", "Rizwan", "Ibrahim"]

Both graph traversals run in O(V + E) — every vertex and every edge is examined once.

Which traversal, when

You need	Use
Shortest path in an unweighted graph	BFS
Level-by-level processing	BFS
Visit everything, order flexible	DFS — usually less code
Detect cycles, topological sort	DFS
Exhaustive path exploration / backtracking	DFS

Grid problems — islands, flood fill, maze paths — are graph problems in disguise: each cell is a node, adjacent cells are edges. The same two traversals solve them.

Practice problems: the Binary Tree, BST, and Graphs sections of the practice catalog.