DepthFirst Search
Published
Completeness   
The graph search variant is complete because it avoids repeated states, redundant paths, and it will eventually visit every node.
The tree search variant is incomplete because it can get stuck in an infinite loop. 
Optimality    Not optimal. 
Time Complexity    O(b^{m}) 
Space Complexity    O(b^{m}) 
Visual Example

 We start from the root node A.
 We check to see if A is a goal node. It's not, so we add it's children, nodes B and C, to the frontier.
 We remove node B from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes D and E, to the frontier.
 We remove node D from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node E from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes H and I, to the frontier.
 We remove node H from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node I from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node C from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes F and G, to the frontier.
 We remove node F from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node G from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes J and K, to the frontier.
 We remove node J from the frontier, we check if it's a goal node. It's not, so we continue.
 We remove node K from the frontier, we check if it's a goal node. It is, so we're done.
Algorithm Notes
 Abbreviated as DFS.
 Uses a LIFO queue for the frontier.
 Although the example given here uses NLR (PreOrder) traversal, you could use LNR (InOrder) or LRN (PostOrder) traversal.
 Each node is explored once and only once.
Return to Articles