Skip to content
Velloreth
Programming 8 min read

Trees and Graphs Explained: Traversal and Real Uses

Trees model hierarchy and graphs model relationships. Learn the structures, the traversal algorithms, and where each appears in real software.

By

A graph is a set of nodes connected by edges. A tree is a graph with two extra constraints: it has no cycles, and it has a single root from which every node is reachable.

That means every tree is a graph, but not every graph is a tree. The constraints are what make trees easier to work with — no cycles means no infinite loops, and a single root means a natural direction of traversal.

Both model relationships. The question is whether the relationships are hierarchical (tree) or arbitrary (graph).

Trees

A tree node holds a value and references to its children.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

A binary tree restricts each node to at most two children, conventionally called left and right.

Terminology

  • Root — the top node, with no parent.
  • Leaf — a node with no children.
  • Depth — the number of edges from the root to a node.
  • Height — the longest path from a node down to a leaf.
  • Subtree — a node and all its descendants.

Where trees appear

The DOM. HTML is a tree. Every element has a parent and children, and the browser traverses it to render and to dispatch events.

File systems. Directories contain files and other directories. Walking a directory tree is a depth-first traversal.

JSON and configuration. Nested objects are trees. Parsing and validating them is tree traversal.

Database indexes. B-trees and B+ trees are why an indexed lookup does not scan the whole table. They are balanced, many-way trees optimised for disk reads.

Compilers. The abstract syntax tree is the central data structure of every parser and compiler.

Organisation charts and category taxonomies. Any hierarchy is a tree.

Binary search trees

A binary search tree adds an ordering invariant: everything in the left subtree is smaller than the node, everything in the right subtree is larger.

class BST {
  #root = null;

  insert(value) {
    const node = { value, left: null, right: null };
    if (!this.#root) { this.#root = node; return; }
    let current = this.#root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.#root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}

Search, insert, and delete are O(log n) when the tree is balanced, because each comparison discards half the remaining nodes — the same halving that makes binary search fast.

The catch is balance. Insert 1, 2, 3, 4, 5 in order and every node goes to the right, producing a linked list with O(n) search. This is not a theoretical concern; it happens whenever you insert sorted data, which is common.

Self-balancing trees fix it by rotating nodes after each insertion to keep the height logarithmic:

  • AVL trees keep the heights of sibling subtrees within one, giving tighter balance and faster lookups.
  • Red-black trees allow more imbalance but fewer rotations, giving faster insertion. Most standard library ordered maps use these.
  • B-trees allow many children per node, which reduces disk reads. Database indexes use these.

Tree traversal

There are two families.

Depth-first goes as deep as possible before backtracking. For binary trees there are three orders:

function inOrder(node, visit) {   // left, node, right — sorted order for a BST
  if (!node) return;
  inOrder(node.left, visit);
  visit(node.value);
  inOrder(node.right, visit);
}

function preOrder(node, visit) {  // node, left, right — used to copy a tree
  if (!node) return;
  visit(node.value);
  preOrder(node.left, visit);
  preOrder(node.right, visit);
}

function postOrder(node, visit) { // left, right, node — used to delete a tree
  if (!node) return;
  postOrder(node.left, visit);
  postOrder(node.right, visit);
  visit(node.value);
}

In-order traversal of a binary search tree visits values in sorted order, which is a useful property and a common interview question.

Breadth-first visits level by level, using a queue:

function levelOrder(root, visit) {
  if (!root) return;
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    visit(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

Level-order traversal is how you compute the height of a tree, print it level by level, or find the minimum depth.

Graphs

A graph is a set of nodes and edges with no hierarchy implied. Edges may be directed (one-way) or undirected (two-way), and weighted or unweighted.

Representation

Adjacency list — a map from each node to its neighbours:

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['D']],
  ['C', ['D']],
  ['D', []],
]);

Adjacency matrix — a 2D grid where matrix[i][j] is true if there is an edge:

const matrix = [
  [0, 1, 1, 0], // A -> B, C
  [0, 0, 0, 1], // B -> D
  [0, 0, 0, 1], // C -> D
  [0, 0, 0, 0], // D
];
Adjacency listAdjacency matrix
SpaceO(V + E)O(V²)
Check edge existsO(degree)O(1)
Iterate neighboursO(degree)O(V)
Best forSparse graphsDense graphs

Most real graphs are sparse — a social network with a million users has far fewer than a trillion friendships — so the adjacency list is the right default.

Where graphs appear

Social networks. People are nodes, friendships are edges. Friend recommendations are graph algorithms.

Maps and routing. Intersections are nodes, roads are weighted edges. Shortest-path algorithms find routes.

Dependency resolution. Packages are nodes, dependencies are directed edges. Installing a package means topologically sorting the graph.

Build systems. Make, Bazel, and Turborepo model targets as a directed acyclic graph and rebuild only what changed.

State machines. States are nodes, transitions are edges.

Recommendation engines. “Users who bought this also bought” is a graph traversal.

Network topology. Routers and links form a graph; routing protocols compute paths through it.

Graph traversal

Breadth-first search explores in order of distance from the start:

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbour of graph.get(node) ?? []) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour);
        queue.push(neighbour);
      }
    }
  }
  return order;
}

BFS finds the shortest path in an unweighted graph, because it reaches every node at distance d before any node at distance d+1.

Depth-first search follows one path to its end before backtracking:

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  for (const neighbour of graph.get(start) ?? []) {
    if (!visited.has(neighbour)) dfs(graph, neighbour, visited);
  }
  return visited;
}

DFS is the basis for cycle detection, topological sorting, connected components, and finding bridges and articulation points.

Topological sort

A topological sort orders a directed acyclic graph so every node comes before the nodes it points to. It is what build systems and package managers do.

function topologicalSort(graph) {
  const visited = new Set();
  const result = [];
  function visit(node) {
    if (visited.has(node)) return;
    visited.add(node);
    for (const dep of graph.get(node) ?? []) visit(dep);
    result.push(node); // post-order: dependencies first
  }
  for (const node of graph.keys()) visit(node);
  return result.reverse();
}

If the graph has a cycle, no valid ordering exists — which is exactly how circular dependency errors are detected.

Shortest paths

For unweighted graphs, BFS gives shortest paths. For weighted graphs with non-negative weights, Dijkstra’s algorithm uses a priority queue:

// Conceptual Dijkstra
// 1. dist[start] = 0, all others = Infinity
// 2. push start into a min-heap keyed by distance
// 3. pop the closest unvisited node
// 4. relax its edges: if dist[u] + w < dist[v], update and push v
// 5. repeat until the heap is empty

Dijkstra runs in O((V + E) log V) with a binary heap. It fails on negative weights, which is what Bellman-Ford handles.

Choosing a traversal

ProblemTraversal
Shortest path, unweightedBFS
Shortest path, weighted, non-negativeDijkstra
Cycle detectionDFS
Topological orderDFS post-order
Connected componentsDFS or BFS
Level-by-level processingBFS
Path existenceEither
Minimum spanning treeKruskal or Prim

Common mistakes

Forgetting to mark nodes visited. In a graph with cycles, this causes infinite recursion. Always mark on enqueue or on visit, and be consistent.

Using recursion for deep graphs. A graph with a million nodes will overflow the call stack. Use an explicit stack.

Assuming a tree is balanced. A binary search tree built from sorted input is a linked list. Use a self-balancing variant or shuffle the input.

Using an adjacency matrix for a sparse graph. A million-node graph needs a trillion-entry matrix. Use a list.

Confusing directed and undirected. A dependency graph is directed; treating it as undirected hides cycles.

For the structures these build on, see data structures every developer should know and stacks and queues explained, which covers the traversals’ underlying containers. For the complexity reasoning, Big-O notation explained.

Quotable summary

A tree is a graph with no cycles and a single root, so there is exactly one path between any two nodes; a graph allows cycles and arbitrary connections. Depth-first traversal uses a stack and suits cycle detection, topological sorting, and connected components; breadth-first traversal uses a queue and finds shortest paths in unweighted graphs. Binary search trees give O(log n) search when balanced but degrade to O(n) when skewed, which is why AVL and red-black trees exist. Graphs are stored as adjacency lists for sparse graphs and adjacency matrices for dense ones, and the list is the right default because most real graphs are sparse. Most problems that look like trees or graphs reduce to choosing the correct traversal.

Frequently asked questions

What is the difference between a tree and a graph?
A tree is a special case of a graph with no cycles and a single root, so there is exactly one path between any two nodes. A graph allows cycles and any node can connect to any other, which makes it more general and more complex to traverse.
What is the difference between BFS and DFS?
Breadth-first search explores all neighbours of a node before going deeper and uses a queue; it finds shortest paths in unweighted graphs. Depth-first search follows one path as far as possible before backtracking and uses a stack; it is better for cycle detection and topological sorting.
What is a binary search tree?
A binary search tree is a tree where every node's left subtree holds smaller values and its right subtree holds larger ones. This ordering allows search, insertion, and deletion in O(log n) time when the tree is balanced.
Why do binary search trees become slow?
Because inserting sorted data makes the tree degenerate into a linked list, where each node has only one child. Search then costs O(n) instead of O(log n). Self-balancing trees like red-black trees and AVL trees prevent this by rotating nodes to keep the height logarithmic.
What is a topological sort?
A topological sort orders the nodes of a directed acyclic graph so that every node comes before all the nodes it points to. It is used for build systems, task scheduling, and dependency resolution, and it is only possible when the graph has no cycles.
How do you detect a cycle in a graph?
For an undirected graph, run a depth-first search and check whether you ever reach an already-visited node that is not the one you came from. For a directed graph, track nodes on the current recursion path and report a cycle if you revisit one.