Exercises: Searching Trees
Apr 092018Before attempting these exercises, you should read the posts on depth-first search (DFS) and breadth-first search (BFS).
Exercises: Searching Lists
Apr 092018Before attempting these exercises, you should read the post on linear and binary search.
Breadth-First Search
Apr 092018Depth-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 092018Search 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 092018Search 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
<h1>tag. - 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)