An algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level, i.e. a node with the minimal depth expanded first and on each level all possibilities are generated first and then solved.

An example: Order in which the nodes are expanded

Properties:

  • Completeness: yes
  • Optimality (Admissibility): yes
  • Time Complexity: O(bd)
  • Space Complexity: O(bd), b – branching factor, d – depth in the tree