DFS (Depth-First Search) is an algorithm for traversing a graph. DFS starts from source vertex (graph) or root (in trees) and then visits an unvisited adjacent node v. After that it checks if node v has any adjacent node which is unvisited. If it reaches a leaf node or any node having no unvisited adjacent node. It backtracks and continue traversing other nodes in the same fashion.
Unlike other linear data structures like Queues and Stacks, Trees and Graphs have more than one logical way to traverse them. Following are the generally used Depth-First traversals for binary trees:
- In-Order
- Pre-Order
- Post-Order
Depth First Traversals of above Binary tree
- Inorder (Left Root Right)
2 1 4 3 5- Preorder (Root Left Right)
1 2 3 4 5- Postorder (Left Right Root)
2 4 5 3 1Implementing DFS in a Binary Tree
Inorder
void inorder (Node *root) {
if (root == NULL)
return;
// traverse left
inorder (root->left);
// print root
cout << root->data << " ";
// traverse right
inorder (node->right);
}
Preorder
void preorder (Node *root) {
if (root == NULL)
return;
// print root
cout << root->data << " ";
// traverse left
preorder (root->left);
// traverse right
preorder (root->right);
}
Postorder
void postorder (Node *root) {
if (root == NULL)
return;
// traverse left
postorder (root->left);
// traverse right
postorder (root->right);
// print root
cout << root->data << " ";
}
Code Implementation
//
// main.cpp
// Depth First Traversal in Binary Tree
//
// Created by Himanshu on 26/08/21.
//
#include <iostream>
#include <queue>
using namespace std;
struct node {
int value = 0;
struct node *left, *right;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->value = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
void inorder (Node *root) {
if (root == NULL) {
return;
}
// traverse left
inorder (root->left);
// print root
cout << root->value << " ";
// traverse right
inorder (root->right);
}
void preorder (Node *root) {
if (root == NULL) {
return;
}
// print root
cout << root->value << " ";
// traverse left
preorder (root->left);
// traverse right
preorder (root->right);
}
void postorder (Node *root) {
if (root == NULL) {
return;
}
// traverse left
postorder (root->left);
// traverse right
postorder (root->right);
// print root
cout << root->value << " ";
}
int main() {
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
cout<<"Inorder traversal:"<<endl;
inorder (root);
cout<<endl;
cout<<"Preorder traversal:"<<endl;
preorder (root);
cout<<endl;
cout<<"Postorder traversal:"<<endl;
postorder (root);
cout<<endl;
return 0;
}
Output
Inorder traversal: 2 1 4 3 5 Preorder traversal: 1 2 3 4 5 Postorder traversal: 2 4 5 3 1
Here’s a working example: DFS (Binary Tree)
Time Complexity
Time complexity of each traversal (Preorder Inorder & Postorder) is O(n). Since after the initial call, the traversal method is called recursively exactly twice for each node in the tree – once for its left child & once for its right child.
Proof
Let T(n) the time taken by the Depth first traversal method.
So for any n > 0, let method is called on node root whose left subtree has k nodes and right subtree has n-k-1 nodes.
For a skewed tree, k = 0, therefore
T(n) = T(0) + T(n-1) + d (d - some constant time for empty tree)
T(n) = 2T(0) + T(n-2) + 2d
T(n) = 3T(0) + T(n-3) + 3d
and similarly,
T(n) = kT(0) + T(n-k-1) + kdLet T(0) = c, for some positive constant c . Going on,
T(n) = (n-1)T(0) + T(0) + (n-1)d
T(n) = nT(0) + (n)d
= (c+d)nImplementing DFS in a Graph
Consider the following graph:
Depth First Search of above Graph for source node to be 1:
1 2 4 5 3 6Pseudocode for DFS
Let G be the graph and s be the source node. We’ll maintain a vis[] (visited) array to mark a node as visited ie for node i, vis[i] is 1 if it has been visited already, otherwise vis[i] will be 0.
DFS (G, s)
vis[s] = 1
for each v ∈ Adjacent(s):
if vis[v] == 0:
DFS(G, v);
end
end
Time complexity for Depth-First Search is O(n) where n is the number of nodes. This is because each node is visited only once.
Note: We advise you to try implementing DFS for a graph yourself before reading the implementation in C++ below:
Implementation
There are various ways to represent a graph, namely:
- Adjacency Matrix
- Adjacency List
and etc. These are explained here.
I find implementing a graph in C++ using an array of vector, very intuitive and efficient. Let’s see..
//
// main.cpp
// DFS in Graph
//
// Created by Himanshu on 27/08/21.
//
#include <iostream>
#include <vector>
using namespace std;
//n = number of nodes in graph
void DFS (int x, int n, vector<int> graph[], int vis[]) {
vis[x] = 1;
cout<<x<<" ";
for (int i=0; i<graph[x].size(); i++) {
int j = graph[x][i];
if (vis[j] == 0) {
DFS(j, n, graph, vis);
}
}
}
int main() {
int s = 1, n = 6;
vector<int> graph[n+1];
int vis[n+1];
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(4);
graph[3].push_back(5);
graph[4].push_back(2);
graph[4].push_back(5);
graph[4].push_back(6);
graph[5].push_back(3);
graph[5].push_back(4);
graph[6].push_back(4);
for (int i=1; i<=n; i++) {
vis[i] = 0;
}
cout<<"Graph:"<<endl;
for (int i=1; i<=n; i++) {
cout<<i<<": ";
for (int j=0; j<graph[i].size(); j++) {
cout<<graph[i][j]<<" ";
}
cout<<endl;
}
cout<<endl<<"DFS:"<<endl;
DFS(s, n, graph, vis);
return 0;
}
Output
Graph: 1: 2 2: 1 4 3: 5 4: 2 5 6 5: 3 4 6: 4 DFS: 1 2 4 5 3 6
Here’s a working example: DFS (Graph)
4 thoughts on “DFS (Depth-First Search) in Binary Trees and Graphs”