I run a service business·I build them

Data Structures

Trees and Graphs

Traverse trees with DFS and BFS, and solve common tree problems.

Binary Trees

A tree where each node has at most two children (left and right).

Common types:

  • Binary Search Tree (BST): Left < root < right
  • Balanced BST (AVL, Red-Black): Height O(log n)
  • Heap: Max or min element always at root

Tree Traversal

DFS (Depth-First Search):

  • Preorder: Root → Left → Right
  • Inorder: Left → Root → Right (gives sorted order for BST)
  • Postorder: Left → Right → Root

BFS (Breadth-First Search): Level by level, uses a queue

Graphs

A graph is a collection of nodes (vertices) connected by edges. More general than trees.

  • DFS: Use recursion or a stack
  • BFS: Use a queue, finds shortest path in unweighted graph

Example

javascript
class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

// DFS Traversals
function inorder(root) {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

// BFS - level order traversal
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [];
    const levelSize = queue.length;
    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;
}

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

// Check if BST is valid
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);
}

// Graph BFS - shortest path
function bfsGraph(graph, start, end) {
  const visited = new Set([start]);
  const queue = [[start, [start]]];
  while (queue.length) {
    const [node, path] = queue.shift();
    if (node === end) return path;
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
  return null;
}

// Nothing above runs on its own. Build one small tree and one small graph,
// then print what each traversal actually returns:
//        4
//      /   \
//     2     6
//    / \   / \
//   1   3 5   7
const tree = new TreeNode(4,
  new TreeNode(2, new TreeNode(1), new TreeNode(3)),
  new TreeNode(6, new TreeNode(5), new TreeNode(7)));

console.log("inorder:", inorder(tree));        // sorted, because it is a BST
console.log("levelOrder:", levelOrder(tree));  // one array per depth
console.log("maxDepth:", maxDepth(tree));
console.log("isValidBST:", isValidBST(tree));

const graph = { a: ["b", "c"], b: ["d"], c: ["d"], d: [] };
console.log("shortest a->d:", bfsGraph(graph, "a", "d"));
Try it yourself — JAVASCRIPT