We will call our first searching tool tree-search, because it is designed to search state spaces that are in the form of trees. It takes four arguments: (1) a list of valid starting states, (2) a predicate to decide if we have reached a goal state, (3) a function to generate the successors of a state, and (4) a function that decides in what order to search. The first argument is a list rather than a single state so that t r e e - sea r c h can recursively call itself after it has explored several paths through the state space.

Think of the first argument not as a starting state but as a list of possible states from which the goal may be reached. This lists represents the fringe of the tree that has been explored so far. t r e e - search has three cases: If there are no more states to consider, then give up and return f a i 1. If the first possible state is a goal state, then return the succesful state. Otherwise, generate the successors of the first state and combine them with the other states. Order this combined list according to the particular search strategy and continue searching. Note that t r e e - search itself does not specify any particular searching strategy.

(defun tree-search (states goal-p successors combiner)