can you add a code thing here so I can practice memorizing the algo here
We have a template here.
the next page has the question with the code thing there
I was led here from “Evaluator”:
Question 4 out of 20
Which algorithm should you use to find a node in a narrow but deep tree when either algorithm works?
Depth First Search
Breadth First Search
You state here that
"DFS is better at:
narrow but deep trees"
Isn’t that a contradiction?
Is there a bug in the Evaluator?
The question, as it is, makes no sense to me. You have the same chances of finding something with the same speed.
The element to search is expected to be closer to the root somehow? Then BFS. If it is in the depths, then DFS might find it quicker.
As an example, imagine yourself searching a book in the 10 boxes split by 5 rows (2 boxes per row). Here is the score table that compares BFS vs DFS:
Bfs vs Dfs
Formula: score[row][col] = number of steps to arrive to that cell using BFS - those of DFS. For example, with BFS at [row 1 col 2] you arrive at second step, while with DFS you run the first column entirely (that’s 5 boxes) + that first box in the second column (total 5+1 = 6).
col 1 col 2
row 1 0 +4
row 2 -1 +3
row 3 -2 +2
row 4 -3 +1
row 5 -4 0
Here, the score sums to 0. That means that BFS is as good as DFS in terms of speed, unless we get any details regarding possible location of our element to find.
Sorry for the messed up spaces in the table. Since I cannot edit my message nor I know how algomonster manages whitespaces (some of them got removed, some not), I just hope it is clear enough. Or unless somebody can fix it
In the template above, the root node is not being checked. Should it be this instead?
from collections import deque
queue = deque([root]) # at least one element in the queue to kick start bfs
while len(queue) > 0: # as long as there is an element in the queue
node = queue.popleft() # dequeue
if OK(node): # early return if problem condition met
for child in node.children: # enqueue children