An algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking, i.e. a node with the highest depth is expanded, nodes with the highest depth are expanded in the same order as generated.  

An example: Order in which the nodes are expanded

Properties:

  • Completeness: no
  • Optimality (Admissibility): no
  • Time Complexity: O(bm)
  • Space Complexity: O(bm), b – branching factor, m – max depth