A depth first search algorithm analyzes the first child node for a match, and if one is not found, then it moves to that nodes children. This repeats until either a depth limit is reached, or there are no more children.
Because of the complexity of some trees, consider a list of all websites to crawl, you may not find an end to your tree, unless you actively prune existing nodes which you’ve searched, or you might run out of computer resources before hitting a specific depth. This is why the depth limit is sometimes added to prevent you from moving too far, and never being able to finish.
While this might seem worse than a breadth first search, due to its nature, a depth first search lends itself better to using a heuristic methods. That is, instead of choosing the next child once a branch has expired, it can choose the among the children and try to determine the best child node to pick.
Now a logical question to ask yourself is, how do you know where to go when you reach the end of your list? Well, you move to the parent, and then the next child of the last element you were at. Keeping track of that might seem difficult, until you realize that a stack would help you perform this task.
Using a logical series of pushes and pops allows you to keep track as to where you are in the tree.
As you traverse each node, it is pushed onto the stack. When you get to the last child of the next to last element, you pop off the last element. At this point you move to the next child of that node and repeat the process of pushing and popping along the tree structure.
This is one way in which different data structures can be used to work together to help solve problems in computer science.
Depth First Searching was originally found on Access 2 Learn
