Karumanchi (pg 216)
DFS
1) Visit a node, then one of its child, then one of its child, till you reach the leaf. Then backtrack and visit other childs.
2) lower memory requirements since its not required to store all child pointers at each level.
3) If data being looked for has more probability of being at the bottom of the tree, then DFS is a good fit.
4) DFS works off a stack
5) Example: Good for solving puzzles such as mazes, finding strongly connected components (Finding Strongly Connected Components of a graph A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex).
6) Simple algo is recursive
BFS
1) more memory than DFS
2) If data being looked for has more probability of being at top of the tree then BFS is a good fit.
3) It visits all vertices at level 1 before proceeding ahead. Then it visits all vertices at level 2. Is similar to level order traversal of trees.
4) BFS works off a queue
5) Example: shortest path,
6) simple algo is non recursive (with a while loop)