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.

## D**ifference** 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.