## 2.9 Search Order

So far we have not specified in which order search trees are explored. Although this order has no impact on the shape and size of a search tree, it does have an impact on the time and memory resources needed to find one or all solutions:

- If we are only interested in one solution, there is no need to explore the entire search tree. Ideally, we would just explore the path leading from the root to the solution.

- If we are interested in all solutions, we need to explore the entire search tree. However, whether we explore the tree in depth-first or breadth-first manner will make a big difference in the memory needed. The memory requirements of breadth-first exploration are typically exponentially larger than those of depth-first exploration.

We will assume that the search engine explores the search trees always in a depth-first fashion. Moreover, when the engine distributes with a constraint , it explores the space obtained with first and the space obtained with second.

The above assumptions ensure that the exploration of a search tree is a deterministic process, provided the distribution strategy generating the constraints to distribute with is deterministic.