Question is about tree search. I believe I understand the differences between DFS, BFS, and IDDFS. In regards to Optimality, Completeness, Time Complexity, and Space Complexity IDDFS has a better performance for tree searches.
So, when would I want to run BFS or DFS instead of IDDFS in a tree search?
Thanks
Here is what we know about DFS and BFS and why we would consider using IDDFS over them:
DFS
DFS traverses nodes starting with one adjacent to the root, then the next adjacent to that node and so on. The issue with this approach can result when the target node is close to the root, but not in the subtree of the first adjacent node traversed by the algorithm. This would result in the algorithm traversing an entire subtree that does not contain the target node which is not very efficient.
BFS
BFS traverses a tree layer by layer. The closer the target node is to the root in terms of depth, the quicker it will be found. This eliminates the issue with DFS if the target node is not in the subtree that is initially traversed. The tradeoff here is that BFS requires more space, O(n) where n is the number of nodes where DFS requires O(d) of space where d is the depth of the tree.
IDDFS
IDDFS combines DFS's space efficiency with BFS's faster search (please note BFS isn't always faster but in many cases, it will find the target node first). IDDFS calls DFS for different depths with an initial value. It is essentially calling DFS in a BFS fashion. The tradeoff here is that IDDFS is much more complicated to implement so it should only really be used if you are concerned with limited BOTH space and time. Otherwise, either BFS or DFS will be sufficient depending on which you prefer.
I hope this information is helpful!