## Introduction

A __binary tree__ is a tree __Data Structure__ where every node has a maximum of two children (could be 0, 1, 2), referred to as the left child and the right child.

BFS (Breadth-First Search) and DFS (Depth-First Search) are tree traversal algorithms. In BFS, we start with the root node and then traverse the tree row by row, and in DFS, we begin with the root node and traverse the tree in depth until we find the node with no children and backtrack it.

## BFS

__Breadth-First Search__ is also known as Level Order Traversal. This algorithm starts with the root node and then visits all nodes level by level from left to right. Here we see every node on a level before going to a lower level. To implement BFS, we use a queue. The Breadth-First Search for trees can be implemented using level order traversal.

### Algorithm

Let us look at the algorithm to implement BFS.

- Start from root
- Insert the root node into BFS and all of that node's neighbours into the queue.
- If the node is not visited, pop it from the queue and add it to BFS, as well as all of its unvisited neighbours.
- Repeat until the queue's size is not equal to zero(NULL).

### Example

#### BFS Implementation

```
#include <iostream>
#include <queue>
using namespace std;
// Structure for holding data, references to the left child and the right child of the current node
struct node {
int data;
struct node *left, *right;
};
// Method for initialising new node with provided data value
node* new_node(int data) {
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
node *root = new_node(5);
root->left = new_node(12);
root->right = new_node(7);
root->left->left = new_node(18);
root->left->left->left = new_node(4);
root->left->left->right = new_node(13);
root->right->right = new_node(69);
cout << "BFS for the above tree will be: \n";
// We will use a queue data structure for maintaining order between nodes
queue<node *> q;
// Pushing the root node into the queue
q.push(root);
// Iterating over the queue until its non empty
while (q.empty() == false){
// Printing the current node from front of the queue
node *node = q.front();
cout << node->data << " ";
// Removing the front node
q.pop();
// Pushing left and right child into the queue only if they exist
// We push the left child first so as to maintain the order
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
return 0;
}
```

Output

```
BFS for the above tree will be:
5 12 7 18 69 4 13
```

**Time Complexity**

Time complexity is the order of n, i.e., O(n), where n is the number of nodes in the tree (each node is visited exactly once).

Must Read __Algorithm Types__

## DFS

In __DFS Algorithm__, we start with the root node and traverse the tree in depth until we find the node with no children and then backtrack it. To implement DFS, we use a stack.

There are 3 types of DFS traversals for Binary trees.

- In-Order (Left-Root-Right)
- Pre-Order (Root-Left-Right)
- Post-Order (Left-Right-Root)

So, the__ Depth-First Search__ for trees can be implemented using pre-order, in-order, and post-order.

### Algorithm

Let us look at the algorithm to implement DFS.

**In-Order Traversal**

Inorder(root):

- Move to the node's left side (traverse left-subtree).
- Print the node's data.
- Move to the node's right side (traverse right-subtree).

**Pre-Order Traversal**

Preorder(root):

- Print the node's data.
- Move to the node's left side (traverse left-subtree).
- Move to the node's right side (traverse right-subtree).

**Post-Order Traversal**

Postorder(root):

- Move to the node's left side (traverse left-subtree).
- Move to the node's right side (traverse right-subtree).
- Print the node's data.

### Example

#### DFS Implementation

```
#include <iostream>
using namespace std;
// Structure for holding data, references to the left child and the right child of the current node
struct node {
int data;
struct node* left, *right;
node(int data) {
this->data = data;
left = right = NULL;
}
};
// For PostOrder traversal, we first recursively print the left child then the right child and then print the parent node
void printPost_order(struct node* node) {
if (node == NULL)
return;
printPost_order(node->left);
printPost_order(node->right);
cout << node->data << " ";
}
// for InOrder traversal, we first recursively print the left child then the parent node and then print the right child
void printIn_order(struct node* node) {
if (node == NULL)
return;
printIn_order(node->left);
cout << node->data << " ";
printIn_order(node->right);
}
// For PreOrder traversal, we first print the parent node then recursively print the left child and then print the right child
void printPre_order(struct node* node) {
if (node == NULL)
return;
cout << node->data << " ";
printPre_order(node->left);
printPre_order(node->right);
}
int main() {
struct node *root = new node(5);
root->left = new node(12);
root->right = new node(7);
root->left->left = new node(18);
root->left->left->left = new node(4);
root->left->left->right = new node(13);
root->right->right = new node(69);
cout << "DFS for the above tree will be:\n";
cout << "\t• Inorder (Left-Root-Right) - ";
printIn_order(root);
cout << "\n\t• Preorder (Root-Left-Right) - ";
printPre_order(root);
cout << "\n\t• Postorder (Left-Right-Root) - ";
printPost_order(root);
return 0;
}
```

Output

```
DFS for the above tree will be:
• Inorder (Left-Root-Right) - 4 18 13 12 5 7 69
• Preorder (Root-Left-Right) - 5 12 18 4 13 7 69
• Postorder (Left-Right-Root) - 4 13 18 12 69 7 5
```

**Time Complexity**

Time complexity is the order of n, i.e., O(n), where n is the number of nodes in the tree (each node is visited exactly once).

Must Recommended Topic, __Binary Tree Postorder Traversal____.__

## Frequently Asked Questions

**What is a Binary Tree?**

A binary tree is a data structure with a maximum of two offspring, known as the left and right children, for each node.

**Types of data structures used for BFS vs DFS?**

Queue type data structure is used in Breadth-First Search(BFS) to store nodes of different levels, and Stack type data structure is used in Depth-First Search(DFS).

**Why time complexity in both BFS and DFS is O(n)?**

Both BFS(Breadth-First Search) and DFS(Depth-First Search) traversal algorithms visit each node exactly once. So, the time complexity in both BFS and DFS is the same, O(n).

**When to use BFS vs DFS?**

The number and placement of solutions are dependent on the topology of the search tree. BFS is better when the target is closer to the source, and DFS is better when the target is far from the start.

**What is the space complexity for BFS vs DFS?**

The space required for traversal in BFS is of the order of width O(w), whereas the space needed for traversal in DFS is of the order of height O(h) of the tree.

## Conclusion

This article extensively discussed BFS(Breadth-First-Search) and DFS(Depth-First-Search) traversal algorithms for Binary Trees. We started with a brief introduction of BFS and DFS, and then we discussed them with the algorithm and example.

After reading about the BFS vs DFS for Binary Tree, are you not feeling excited to read/explore more articles on the topics related to Binary Tree, BFS, and DFS…? Don't worry; Coding Ninjas has you covered. To learn, see __Binary Tree__, __BFS__, and __DFS__.

**Recommended Readings**:

**Recommended Problems** -

__Vertical Order Traversal of a Binary Tree____Leaf Nodes in Binary Tree____Binary Array Sorting____Mirror A Binary Tree__

Refer to our __Guided Path__ on __Coding Ninjas Studio__ to upskill yourself in __Data Structures and Algorithms__, __Competitive Programming__, __JavaScript__, __System Design__, and many more! If you want to test your competency in coding, you may check out the mock __test series__ and participate in the __contests__ hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the __problems__, __interview experiences,__ and __interview bundle__ for placement preparations.

Nevertheless, you may consider our paid __courses__ to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!