Last Updated: Jul 2, 2023
Medium

# BFS vs DFS for Binary Tree

Sanchit Kumar

## Introduction

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.

1. Start from root
2. Insert the root node into BFS and all of that node's neighbours into the queue.
3. If the node is not visited, pop it from the queue and add it to BFS, as well as all of its unvisited neighbours.
4. 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).

## 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):

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

Pre-Order Traversal

Preorder(root):

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

Post-Order Traversal

Postorder(root):

1. Move to the node's left side (traverse left-subtree).
2. Move to the node's right side (traverse right-subtree).
3. 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.

### 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 TreeBFSand DFS.