Non-recursive depth first search algorithm [closed]

by

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.

More Related Contents:

  1. How to efficiently build a tree from a flat structure?
  2. What is the difference between tree depth and height?
  3. Iterating over a Binary Tree with O(1) Auxiliary Space
  4. In Order Successor in Binary Search Tree
  5. Hashing a Tree Structure
  6. reconstructing a tree from its preorder and postorder lists
  7. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  8. Why DFS and not BFS for finding cycle in graphs
  9. Print the biggest K elements in a given heap in O(K*log(K))?
  10. Iterative tree walking
  11. How do I create a URL shortener? [closed]
  12. Segmented Sieve of Eratosthenes?
  13. How do I calculate a point on a circle’s circumference?
  14. How can building a heap be O(n) time complexity?
  15. Is there an O(n) integer sorting algorithm?
  16. Which algorithm is faster O(N) or O(2N)?
  17. Determine font color based on background color
  18. Nearest neighbors in high-dimensional data?
  19. Bitwise and in place of modulus operator
  20. Calculate largest inscribed rectangle in a rotated rectangle
  21. How Can I Best Guess the Encoding when the BOM (Byte Order Mark) is Missing?
  22. Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k
  23. How does Dijkstra’s Algorithm and A-Star compare?
  24. How to cartoon-ify an image programmatically?
  25. Permute all unique enumerations of a vector in R
  26. Is there any fast method of matrix exponentiation?
  27. Easiest algorithm of Voronoi diagram to implement? [closed]
  28. Calculating frames per second in a game
  29. Why are hash table expansions usually done by doubling the size?
  30. Find local minimum in n x n matrix in O(n) time

Leave a Comment