Searching + DFS + BFS Flashcards
What is an important requirement with the data when using a binary search algorithm?
The data needs to be sorted
What is the average case TC for a binary search?
O(logn)
What is the average case TC for traversing a tree or graph?
O(n)
If graph/tree traversal is
What order would this tree be searched with DFS?
9
4 20
1 6 15 170
9, 4, 20, 1, 6, 15, 170
Why does BFS require additional memory?
Because it needs to track all the child nodes on a specific level as it searches that level
What order would this tree be searched with DFS?
9
4 20
1 6 15 170
9, 4, 1, 6, 20, 15, 170
What would you use if you know a solution is not far from the root of a tree?
BFS because it starts at the closest nodes from the top
What would you use if the tree is very deep and solutions are rare?
BFS, because DFS would end up taking a very long time to traverse…?
What would you use if the tree is very wide?
DFS, because BFS will need too much memory
What would you use if solutions are frequent but located deep in the tree?
DFS
What would you use to determine whether a path exists between two nodes?
DFS
What data structure should we use to keep track of children nodes in a BFS algorithm?
Queue
What are the three ‘orders’ of a DFS? Perform each on this tree:
9
4 20
1 6 15 170
- InOrder: [9, 4, 1, 6, 20, 15, 170]
- PreOrder: [1, 4, 6, 9, 15, 20, 170]
- PostOrder: [1, 6, 4, 15, 170, 20, 9]
What are the pros and cons of using BFS in a graph?
Pros: good for finding shortest path between nodes
Cons: more memory is used to store child nodes
