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
Binary Tree

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:

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

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

Leave a Reply

Your email address will not be published.