# DFS (Depth-First Search) in Binary Trees and Graphs

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 1

### Implementing 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 << " ";
}


Here’s a working example:

https://ideone.com/yKcGBR

### 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) + kd

Let 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)n

### Implementing 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 6

### Pseudocode 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 ivis[i] is 1 if it has been visited already, otherwise vis[i] will be 0.

DFS (G, s)
vis[s] = 1
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:

and etc.

I find implementing a graph in C++ using an array of vector, very intuitive and efficient. Let’s see..

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);
}
}
}



Here’s a working example:

https://ideone.com/GQDBW1