Trees & Graphs

Trees and graphs are the most versatile data structures in interviews. Understanding how to traverse them unlocks a huge range of problems.

Tree Traversals

Every tree problem starts with traversal. There are four main types:

        1
       / \
      2   3
     / \   \
    4   5   6

Traversal	Order	Result
Preorder	Root → Left → Right	[1, 2, 4, 5, 3, 6]
Inorder	Left → Root → Right	[4, 2, 5, 1, 3, 6]
Postorder	Left → Right → Root	[4, 5, 2, 6, 3, 1]
Level-order	Level by level	[1, 2, 3, 4, 5, 6]

// Recursive traversals
function preorder(root, result = []) {
  if (!root) return result;
  result.push(root.val);      // Visit root
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);      // Visit root
  inorder(root.right, result);
  return result;
}

function postorder(root, result = []) {
  if (!root) return result;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val);      // Visit root
  return result;
}

// Level-order (BFS)
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

---

Essential Tree Problems

Problem: Maximum Depth of Binary Tree

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Problem: Invert Binary Tree

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

Problem: Check if Two Trees Are the Same

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q || p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Problem: Diameter of Binary Tree

Find the longest path between any two nodes (may not pass through root).

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function height(node) {
    if (!node) return 0;
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);

    // The diameter through this node
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

    return 1 + Math.max(leftHeight, rightHeight);
  }

  height(root);
  return maxDiameter;
}

Problem: Lowest Common Ancestor (LCA)

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;  // p and q on different sides
  return left || right;            // Both on same side
}

Problem: Validate Binary Search Tree

function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;

  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

Problem: Serialize and Deserialize Binary Tree

function serialize(root) {
  if (!root) return 'null';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const nodes = data.split(',');
  let index = 0;

  function buildTree() {
    if (nodes[index] === 'null') {
      index++;
      return null;
    }

    const node = new TreeNode(parseInt(nodes[index++]));
    node.left = buildTree();
    node.right = buildTree();
    return node;
  }

  return buildTree();
}

---

Graph Algorithms

Graph Representations

// Adjacency list (most common for interviews)
const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3, 4],
  3: [1, 2],
  4: [2]
};

// For weighted graphs:
const weightedGraph = {
  0: [[1, 4], [2, 1]],   // [neighbor, weight]
  1: [[0, 4], [3, 1]],
  2: [[0, 1], [3, 5], [4, 2]],
};

DFS on Graph

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

  function explore(node) {
    if (visited.has(node)) return;
    visited.add(node);
    console.log(node);

    for (const neighbor of graph[node]) {
      explore(neighbor);
    }
  }

  explore(start);
}

// Iterative DFS (use stack instead of call stack)
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
}

Classic Problem: Number of Islands

function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0';  // Mark as visited
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

Classic Problem: Clone Graph

function cloneGraph(node) {
  if (!node) return null;
  const clones = new Map();  // original → clone

  function dfs(n) {
    if (clones.has(n)) return clones.get(n);

    const clone = { val: n.val, neighbors: [] };
    clones.set(n, clone);

    for (const neighbor of n.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }

    return clone;
  }

  return dfs(node);
}

Classic Problem: Course Schedule (Cycle Detection)

Can you finish all courses given prerequisites?

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course);
  }

  // 0 = unvisited, 1 = visiting (in current path), 2 = visited
  const state = new Array(numCourses).fill(0);

  function hasCycle(node) {
    if (state[node] === 1) return true;   // Back edge = cycle
    if (state[node] === 2) return false;  // Already processed

    state[node] = 1;  // Mark as in-progress

    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }

    state[node] = 2;  // Mark as done
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }

  return true;
}

Classic Problem: Word Ladder (BFS Shortest Path)

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

  while (queue.length > 0) {
    const [word, length] = queue.shift();

    if (word === endWord) return length;

    // Try changing each character
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);

        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, length + 1]);
        }
      }
    }
  }

  return 0;
}

---

Advanced: Dijkstra's Algorithm

Find shortest path from source to all nodes in a weighted graph.

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();

  // Initialize distances
  for (const node in graph) distances[node] = Infinity;
  distances[start] = 0;

  // Min-heap: [distance, node]
  const heap = [[0, start]];

  while (heap.length > 0) {
    // Extract minimum (simplified — use real min-heap in production)
    heap.sort((a, b) => a[0] - b[0]);
    const [dist, node] = heap.shift();

    if (visited.has(node)) continue;
    visited.add(node);

    for (const [neighbor, weight] of graph[node]) {
      const newDist = dist + weight;

      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        heap.push([newDist, neighbor]);
      }
    }
  }

  return distances;
}

---

Practice Problems

Tree Problems

LeetCode	Problem	Difficulty
104	Maximum Depth of Binary Tree	Easy
226	Invert Binary Tree	Easy
100	Same Tree	Easy
572	Subtree of Another Tree	Easy
235	LCA of BST	Medium
102	Binary Tree Level Order Traversal	Medium
98	Validate BST	Medium
105	Construct Tree from Preorder and Inorder	Medium
543	Diameter of Binary Tree	Easy
110	Balanced Binary Tree	Easy
124	Binary Tree Max Path Sum	Hard
297	Serialize/Deserialize Binary Tree	Hard

Graph Problems

LeetCode	Problem	Difficulty
200	Number of Islands	Medium
133	Clone Graph	Medium
207	Course Schedule	Medium
210	Course Schedule II	Medium
127	Word Ladder	Hard
417	Pacific Atlantic Water Flow	Medium
323	Number of Connected Components	Medium
684	Redundant Connection	Medium
743	Network Delay Time	Medium
787	Cheapest Flights within K Stops	Medium