Depth-First Search

The implementation of this algorithm is done using recursion with the LIFO stack data structure and it creates the same nodes as our first method but in a different order. The space requirement is quite linear since nodes on a single path are stored in each iteration from root-to-leaf node.

The disadvantage of the algorithm is that there's a possibility that this algorithm may not terminate and go on infinitely on one path and in some cases the execution time increases. It can't check for duplicate nodes.

Read more at: https://en.wikipedia.org/wiki/Depth-first_search

Get Learning Android Game Development now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.