Tree Search and Hash Table
- Generic approach to graph(Tree) search:
- DFS: search as far down a single path as possible before backtracking
- how to keep track of where to search next? stack(LIFO)
- can be implemented iteratively(node stack)/recursively(call stack)
- BFS: level order traversal
- how to keep track of where to search next? queue(FIFO)
- DFS: search as far down a single path as possible before backtracking
- Should we use dfs or bfs in PA2? Doesn't really matter. We need to traverse all nodes anyway.
REFERENCE: UCSD CSE100 Data Structure Podcast 01/25/17