Before attempting these exercises, you should read the post on linear and binary search.
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.
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 problems are problems which ask us to find something, given a description of it. Typical search problems are like these:
- Given a list, find the index of a target value.
- Given a list of numbers, find the first negative number.
- Find the first non-empty line in a text file.
- Find all rows in an SQL database table matching a given WHERE clause.
- Given a tree, find a node which holds a target value.
- Given an HTML document, find the first
- Find all tags in an HTML document matching a given CSS selector.
- Starting at a given node in a graph, find all nodes reachable via edges.
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)