Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

BFS vs DFS for Binary Tree

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

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).

Must Read Algorithm Types

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

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

Recommended Readings:

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview experiences, and interview bundle for placement preparations.

You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

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

Happy Learning!

Topics covered
1.
Introduction
2.
BFS
2.1.
Algorithm
2.2.
Example
2.2.1.
BFS Implementation
3.
DFS
3.1.
Algorithm
3.2.
Example
3.2.1.
DFS Implementation
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
Types of data structures used for BFS vs DFS?
4.3.
Why time complexity in both BFS and DFS is O(n)?
4.4.
When to use BFS vs DFS?
4.5.
What is the space complexity for BFS vs DFS?
5.
Conclusion