Data Structures and Algorithms

Breadth-First Search

Apr 092018

Depth-first search (DFS) is a fundamental algorithm for working with trees, because it gives us a way to “visit” every node in the tree, once each.(1) That’s important, because visiting every node is a subproblem of many other problems on trees.

DFS explores the full depth of one subtree before moving onto the next one. If that’s the order we want to visit the nodes in, or the order doesn’t matter, then DFS is fine; otherwise, we need a different algorithm. We’ll see one in this post.

Depth-First Search

Apr 092018

Search problems vary in two ways: what do we want to search for, and what type of collection are we searching in?(1)

When we need a search algorithm, the data structure we want to search is more important than what we want to find. We could even say that linear search and binary search work on different data structures: linear search uses a list, and binary search uses a list which must be kept in order.(2)

Search Algorithms

Apr 092018

Search problems are problems which ask us to find something, given a description of it. Typical search problems are like these:

A search algorithm is one which solves a search problem. In this post, we’ll see two algorithms which solve search problems on lists.(1)


hosted on werp.site