14.2 Tree and Graph Search Algorithms

Tree and Graph Traversal Algorithms

Tree and graph traversal algorithms give you systematic ways to visit every node in a data structure. DFS and BFS take fundamentally different approaches to this problem, and choosing the right one depends on what you're trying to accomplish.

These traversal techniques show up everywhere in computer science: finding shortest paths, detecting cycles, identifying connected components, and powering more advanced graph algorithms like Dijkstra's and Bellman-Ford.

DFS and BFS for Traversal

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. Think of it like navigating a maze by always taking the next available turn and only retracing your steps when you hit a dead end.

• Implemented with a stack (explicit or via recursion)
• For graphs, you must mark nodes as visited to avoid infinite loops in cyclic structures
• DFS has three traversal orders for binary trees:
  • Pre-order: Visit root → traverse left subtree → traverse right subtree. Useful for copying a tree or evaluating expression trees.
  • In-order: Traverse left subtree → visit root → traverse right subtree. On a BST, this produces elements in sorted order.
  • Post-order: Traverse left subtree → traverse right subtree → visit root. Useful for deleting a tree or evaluating postfix expressions.

Breadth-First Search (BFS) explores level by level, visiting all neighbors of a node before moving deeper.

• Implemented with a queue
• For trees, BFS visits every node at depth $d$ before visiting any node at depth $d+1$
• For graphs, you again mark visited nodes to prevent revisiting. BFS naturally finds the shortest path (by number of edges) from the starting node, which is why it's used in applications like social network friend suggestions and web crawlers.

Complexity of Search Algorithms

DFS and BFS share the same asymptotic complexity, but their space usage behaves differently in practice.

Time complexity:

• DFS: $O(V + E)$ — each vertex and edge is processed exactly once
• BFS: $O(V + E)$ — same reasoning; every vertex is dequeued once, and every edge is examined once

Space complexity (both $O(V)$ in the worst case, but for different reasons):

• DFS: The stack (or recursion call stack) can grow as deep as the number of vertices. Worst case is a skewed tree or a graph shaped like a linked list, where depth equals $V$.
• BFS: The queue can hold all vertices at a single level. Worst case is a star graph or the bottom level of a complete binary tree, where up to $O(V)$ nodes sit in the queue at once.

Tree Search Algorithms

Search in Tree Structures

A binary search tree (BST) organizes data so that for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property makes searching efficient.

Searching a BST:

1. Compare the target value to the current node's value.
2. If the target is smaller, move to the left child.
3. If the target is larger, move to the right child.
4. If the target equals the current node's value, the search succeeds.
5. If you reach a null child, the value isn't in the tree.

Time complexity depends entirely on tree shape:

• Balanced BSTs (AVL trees, Red-Black trees) guarantee $O(\log n)$ for search, insertion, and deletion. They enforce a height constraint — for example, AVL trees require the height difference between left and right subtrees of any node to be at most 1.
• Unbalanced BSTs can degenerate into a linked list (imagine inserting 1, 2, 3, 4, 5 in order). In that case, search becomes $O(n)$.

Applications of Search Algorithms

Shortest Path Problems

Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights.

1. Initialize the source distance to 0 and all other distances to infinity.
2. Add all vertices to a priority queue (min-heap) keyed by tentative distance.
3. Extract the vertex $u$ with the smallest tentative distance.
4. For each neighbor $v$ of $u$, check if the path through $u$ is shorter than $v$'s current tentative distance. If so, update $v$'s distance (this is called edge relaxation).
5. Repeat until the priority queue is empty.

• Time complexity: $O((V + E) \log V)$ with a binary heap, or $O(V^2)$ with a simple array

Bellman-Ford algorithm also solves single-source shortest paths but handles negative edge weights.

1. Initialize the source distance to 0 and all others to infinity.

2. Relax all edges $V - 1$ times (since the longest shortest path can have at most $V - 1$ edges).

3. Run one more pass over all edges. If any distance decreases, a negative-weight cycle exists (meaning no valid shortest path).

• Time complexity: $O(VE)$, which is slower than Dijkstra's but necessary when negative weights are present

Connected Components

You can identify all connected components in an undirected graph using either DFS or BFS:

1. Pick any unvisited vertex and run DFS or BFS from it.
2. Every vertex reached during that traversal belongs to the same connected component.
3. Repeat from another unvisited vertex until all vertices have been visited.

• Time complexity: $O(V + E)$ for the entire process, since each vertex and edge is visited exactly once across all traversals