Generalized tree search (DFS, BFS)

generalized-tree-search.md

Generalized Tree Search

A generalized depth and breadth-first tree search algorithm

Here's a neat little algorithm that can perform a depth-first search (DFS) or breadth-first search (BFS) by simply changing the collection data type:

search( Node root ) {
    Collection c = new Collection()
    c.push( root )
    while ( !c.isEmpty() ) {
        Node n = c.pop()
        visit( n )
        c.pushAll( n.children() )
    }
}

• For a depth-first search, make the collection a stack, last-in, first-out (LIFO)

• For a breadth-first search, make the collection a queue, first in, first out (FIFO)

Algorithmic complexity

This algorithm has O(n) runtime complexity, and O(n) space complexity (where n is the total number of nodes in the tree).

In JavaScript

• Use an Array for the queue
• Use push/shift for DFS/FILO
• Use push/pop for BFS/FIFO.

Credit

Credit to @codetothepoint and his CS professor in college

You should add the ability to use this as "Dijkstra's" by making the collection a priority queue, where the priority being the total distance from your initial root node to the node you're inserting into the queue.

I saw this response in a thread and wanted to star your useful gist.