BFS vs DFS for Binary Tree

Difficulty Level Easy
Frequently asked in Amazon Infosys MAQ TCS
Breadth First Search Depth First Search Theory TreeViews 2402

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:

  1. Preorder Traversal
  2. Inorder Traversal
  3. 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.

Reference

Interview Questions

Translate »