CS102: Introduction to Computer Science II

Watch this lecture, which illustrates the role of searching in helping to solve many problems. Searching a tree involves traversing the tree and making a decision at each node as we traverse or step through the tree.  Most problems involve making decisions.  If we can put a value on the outcome of a decision and if we search for a decision that has a 'best' value, then our decision process would be a search process.

The lecture points out two common techniques for traversing all of the elements of a tree: breadth first and depth first search. A traversal technique involves deciding which descendant (sub) element to look at next. Note that the starting large decision has been decomposed into a series of decisions as to which descendent element to look at on the next level down in the tree hierarchy.