BFS vs DFS

http://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

看到 geek for geek 分享的 BFS vs DFS for binary tree 覺得解釋很清楚 特別紀錄一下

Is there any difference in terms of Time Complexity?
All four traversals require O(n) time as they visit every node exactly once.

Is there any difference in terms of Extra Space?
There is difference in terms of extra space required.

1. Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level.
2. Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.

時間複雜度都是 O(n) 但是空間複雜度有差 BFS看每層寬度 DFS看深度

It is evident from above points that extra space required for Level order traversal is likely to be more when tree is more balanced and extra space for Depth First Traversal is likely to be more when tree is less balanced.

How to Pick One?

1. Extra Space can be one factor (Explained above)
2. Depth First Traversals are typically recursive and recursive code requires function call overheads.
3. The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

選擇時 DFS 因為常用Recursive寫 需要考慮stack overhead 的問題.