Non-recursive depth first search algorithm

mousey picture mousey · Mar 11, 2011 · Viewed 116.3k times · Source

I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.

Answer

biziclop picture biziclop · Mar 11, 2011

DFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

BFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.append( currentnode.children );
  //do something
}

The symmetry of the two is quite cool.

Update: As pointed out, take_first() removes and returns the first element in the list.