2 min read

BFS vs DFS for Binary Tree

BFS is better when target is closer to Source. DFS is better when target is far from source. As BFS considers all neighbour so it is not suitable for decision tree used in puzzle games. DFS is more suitable for decision tree
BFS vs DFS for Binary Tree

What are BFS and DFS for Binary Tree?
A Tree is typically traversed in two ways:

  • Breadth First Traversal (Or Level Order Traversal)
  • Depth First Traversals

                    Inorder Traversal (Left-Root-Right)

                    Preorder Traversal (Root-Left-Right)                

                    Postorder Traversal (Left-Right-Root)

https://media.geeksforgeeks.org/wp-content/cdn-uploads/2009/06/tree12.gif

BFS and DFSs of above Tree Breadth First Traversal : 1 2 3 4 5

Depth First Traversals- Preorder Traversal : 1 2 4 5 3 Inorder Traversal  :  4 2 5 1 3 Postorder Traversal : 4 5 2 3 1

Why do we care?
There are many tree questions that can be solved using any of the above four traversals. Examples of such questions are size, maximum, minimum, print left view, etc.

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

How to Pick One?

  1. Extra Space can be one factor
  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.
BFS vs DFS for Binary Tree - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

#Tree #BinaryTree #BFS #DFS #Data #Structures #Probyto #ProbytoAI

Subscribe and follow us for latest news in Data Science and Machine learning and stay updated!
Facebook: https://facebook.com/probyto
Twitter: https://twitter.com/probyto
LinkedIn: https://linkedin.com/company/probyto
Instagram: https://instagram.com/probyto