Table of Contents
Breadth First Search (BFS)
Do we already know about what actually BFS is? if not then don’t need to feel bad just read the whole article and visit our previous article on Breadth First Search for better understanding. BFS is a level order traversal in which we visit the nodes of a binary tree from left to right at every level.
By the use of a Queue data structure, we find the level order traversal. We start from root then we insert root into BFS and insert all neighbors of that node to queue. After that pop the node from the queue and add it to BFS if it is not visited and add it’s all neighbor (unvisited) to queue. Repeat it till the size of the queue is not equal to null.
Depth First Search (DFS)
Are we also aware of what actually DFS is? You can visit our previous article on Depth First Search. DFS of a BT is three types of traversal:
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
Preorder Traversal
Algorithm: Preorder(root): Step:1 Print the data of the Node. Step:2 Move to the left side of the node(traverse left-subtree). Step:3 Move to the right side of the node(traverse right-subtree).
Inorder Traversal
Algorithm: Inorder(root): Step:1 Move to the left side of the node(traverse left-subtree). Step:2 Print the data of the Node. Step:3 Move to the right side of the node(traverse right-subtree).
Postorder Traversal
Algorithm: Postorder(root): Step:1 Move to the left side of the node(traverse left-subtree). Step:2 Move to the right side of the node(traverse right-subtree). Step:3 Print the data of the Node.
Difference between BFS and DFS of a binary tree
Type of data structure used
In BFS we use a queue type data structure and in DFS we use a stack type data structure.
Space Complexity
In BFS we use a queue to store the elements of the level so maximum space used in BFS is O(w) where w is the maximum element in one level. In DFS we use stack and follow the concept of depth. So, the maximum height of the tree is taking maximum space to evaluate. So space complexity of DFS is O(H) where H is the height of the tree.
Time Complexity
The time complexity of both the cases will be O(N+E) where N denotes total nodes in BT and E denote total edges in BT.
Searching a node nearest to the root node
For getting the best result we use BFS for search such type of nodes that is nearest to the root node because it follows level order traversal.
Searching a node away from the root node
For getting the best result we use DFS in this case because it follows the depth concept.
Meaning
BFS meaning Breadth-first search and DFS meaning Depth-first search.
Type of Data Structure used
BFS used Queue type data structure and DFS used Stack type data structure.
Basic
BFS is a vertex-based algorithm and DFS is an edge-based algorithm.
Speed
BFS is slower than DFS.