Tree Search
Tree search is the way of exploring a state space by growing a search tree: the root is the initial state, each child is a state reached by one action from its parent, and the algorithm repeatedly picks a leaf, tests it against the goal, and expands it into children. The search tree is not the state space itself but an unfolding of it, a record of paths tried, so the same state can appear on many branches. This distinction between the space and the tree explored inside it is the source of both the method's simplicity and its main weakness, which is the risk of re-examining what has already been examined.
The decisive difference between tree search and graph search is the treatment of repeated states. Plain tree search keeps no memory of where it has been, so in any problem with reversible actions it will generate loops: in the 8-puzzle, sliding the blank left and then right returns to the start, and a tree search will happily include that detour. In the worst case a state space with only a modest number of states yields a search tree that is infinite or astronomically larger. Graph search remedies this by maintaining an explored set, sometimes called the closed list, and discarding any newly generated state that has been seen before, or, in cost-sensitive search, keeping only the cheaper route. The price is memory proportional to the number of states stored, and a subtle correctness condition: A-star with graph search is optimal only if its heuristic is consistent, not merely admissible, or else it must reopen nodes already closed.
Iterative deepening, analyzed by Richard Korf in a 1985 paper in the journal Artificial Intelligence, resolved the standing dilemma between breadth-first and depth-first search. Breadth-first search is complete and finds shallowest solutions but needs memory exponential in depth; depth-first search is frugal with memory but can chase an endless branch and misses shallow solutions. Iterative-deepening depth-first search runs depth-first search with a depth limit of 0, then 1, then 2, and so on until a goal appears, so it behaves like breadth-first search in what it finds while using memory only linear in depth. The apparent waste of regenerating the upper levels on every pass is small, because in a tree with a large branching factor almost all nodes sit on the deepest level: with a branching factor of 10 and a solution at depth 5, iterative deepening generates about 123,000 nodes against about 111,000 for breadth-first, an overhead near eleven percent. Korf showed that, among brute-force methods, it is asymptotically optimal in time, space and solution length. His IDA-star, from the same year, applies the idea to A-star with a cost threshold in place of a depth limit.
The names themselves breed a misconception: a tree search does not require the problem to be a tree. The label describes the shape of the data the algorithm builds, not the shape of the problem; nearly every interesting problem is a graph, and tree search simply treats it as one by ignoring repeats. Another confusion is between the strategy and the structure. Breadth-first, depth-first, uniform-cost and A-star can each be run as tree search or as graph search, and the choice of strategy, which decides which leaf to expand next, is independent of the choice of whether to remember visited states. In practice, depth-first and iterative-deepening searches often run as tree search on purpose, accepting some duplicated work to save memory, while a route planner will certainly keep a closed set.
Variants of tree search remain central to current systems. IDA-star with pattern databases let Korf and later researchers find optimal solutions to random instances of Rubik's Cube, a result reported at AAAI in 1997. Game programs run depth-limited searches with iterative deepening because it provides an answer at every depth and a natural place to stop when the clock runs out; transposition tables, which record previously evaluated positions, are the game-playing form of an explored set. Monte Carlo tree search, introduced in 2006 by Rémi Coulom and by Levente Kocsis and Csaba Szepesvári, grows the tree asymmetrically toward promising lines using random simulations, and was a core ingredient of AlphaGo. Recent reasoning methods that branch, score and prune candidate thoughts in language models also build explicit trees.
Read tree search as the practice of growing a tree of paths from the start state: the algorithm's choices are how to pick the next leaf and whether to remember repeated states, and iterative deepening is the classic answer to getting breadth-first's guarantees with depth-first's memory.