Given a family tree if one were looking for someone on the t

Given a family tree if one were looking for someone on the tree who\'s still alive, which traversal algorithm among BFS and DFS will be faster? If one were looking for a family member who died a very long time ago, which traversal algorithm among BFS and DFS will be faster? Give reasoning for both answers.

Solution

Rules of thumb for BFS and DFS:-

If you know a solution is not far from the root of the tree, a breadth-first search (BFS) might be better. If the tree is very deep and solutions are rare, depth-first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth-first search (DFS).

If looking for someone on the tree who still alive then it would be safe to assume that person would be on the bottom of the tree.

This means that a BFS would take a very long time to reach that last level.

A DFS, however, would find the goal faster . But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS.