Traversal Techniques

Introduction

Have you ever searched for something in a room and found yourself looking in every corner, every drawer, every shelf until you finally found what you were looking for? Well, that is a kind of traversal technique!

Traversing or navigating across data structures like arrays, lists, trees, or graphs to access, search and process the data are known as traversal techniques in computer science. It is like exploring a maze or a map to find your way to a specific location or information.

The objective of traversal techniques is to visit each element or node in a data structure in a predetermined order repeastedly and without skipping any. Just like when you are searching for something, you don't want to miss a spot or go back to a spot you have already searched.

Different Types of Traversal Techniques

So, you know how sometimes you have to walk through a bunch of stuff, like a list or a tree or some other data structure, and access each element one by one? This is where traversal skills come to help.

There are various ways to traverse these data structures, which we refer to as traversal techniques. Each strategy has advantages and disadvantages, and depending on your goals, you may favour one over the others.

Following is a list of some of the most common traversal techniques:

DFS (Depth First Search) Traversal

In-Depth First Search, the algorithm visits the starting node and then explores as far as possible along each branch before backtracking. There are different ways of doing Depth First Search traversal, such as Pre Order, In Order, and Post Order traversal.

• Pre Order Traversal: If we consider a binary tree, it can be disintegrated into three main components, the root node, left node, and right node. In pre-order traversal, the entry list goes like first the root node, then the left node, and then the right node.
• In Order Traversal: Here, the traversal is slightly different. If we consider the same binary tree, the traversal list first takes in the left node, then the root node, and then the right node.
• Post Order Traversal: In this, the left and the right node is traversed first and then the root node.

BFS (Breadth First Search) Traversal

In Breadth First Search, the algorithm starts at the root node and visits all the nodes at the present depth level before moving on to the nodes at the next depth level. Breadth First Search ensures that all the nodes at a certain depth level are visited before moving on to the nodes at the next depth level. This process continues until all the nodes have been visited.

Let’s look into each of the traversal techniques in detail.

In Order Traversal

In-order traversal is a way to traverse a binary tree data structure where the left subtree of a node is visited, then the node itself, and finally, the right subtree of the node is visited.

Here is how the in-order traversal works:

• First, we start at the root node of the binary tree.
• Then we traverse the left subtree of the root node recursively, visiting each node in the order of the in-order traversal.
• Then we visit the root node itself.
• Next, we need to traverse the right subtree of the root node recursively, visiting each node in the order of the in-order traversal.

Here is an example of the working in-order traversal works:

Suppose we have a binary tree with the following structure:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

To perform an in-order traversal of this binary tree, we start at the root node 4, then traverse the left subtree 2-1-3 in order, visit the root node 4, and finally traverse the right subtree 6-5-7 in order.

The resulting traversal sequence is:

1-2-3-4-5-6-7

In-order traversal can be useful for various applications, such as sorting a binary search tree, finding the Kth smallest or largest element in a binary tree, or validating that a binary tree is a valid binary search tree.

For example, suppose we have a binary search tree with the following structure:

       5
     /   \
    3     8
   / \   / \
  1   4 6   9

If we perform an in-order traversal of this binary search tree, the resulting traversal sequence looks like this:

1-3-4-5-6-8-9

This sequence is sorted in ascending order, which means we can use the in-order traversal to sort the elements of a binary search tree.

Let’s see the code implementation of in-order traversal in C.

Example:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
void inorderTraversal(struct Node* node) {
    if (node == NULL) {
        return;
    }
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
    return newNode;
}
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
printf("In Order Traversal: ");
inorderTraversal(root);
    return 0;
}

Output:

The output of this code is: In Order Traversal: 4 2 5 1 6 3 7

PreOrder Traversal

Let’s discuss another type of traversal technique to visit every node in a tree data structure. In this traversal method, we first move to the root node, followed by the left node, and then the right node gets traversed. This is the reason it is called a pre-order, as the root node is visited before both its child node.

The algorithm of pre order traversal is as follows:

• Check the root node whether it is NULL or not.
• Visit the root node.
• Traverse the left child of the root node recursively.
• Traverse the right child of the root node recursively.

Let’s understand pre-order traversal with an example.

Suppose a tree is given as

        4
      /   \
     2     6
    / \   / \
  1   3 5   7

Pre-order traversal would direct us to begin at the root node, which is 4. Following that, we would see its left child, i.e., 2. Then we would see the left child of 2, i.e., 1. We would go back to 2, as 1 has no next child. Then, we would go see the right child of 2, which is 3. Again, we go back to the 2 and then to 4 as we visited all the left child nodes of 4. Now Let's move the right child of the 4, i.e., 6. Again, use pre-order traversal and go to the left child of 6, i.e., 5. Next, go back to 6 as no child nodes are present 5. So, at last, move to the right child of 6, i.e., 7, and we are done. No, any node remains to visit.

Hence the output of this pre order traversal is: 4 2 1 3 6 5 7

Let’s see the code implementation of pre order traversal in C.

Example:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
void preorderTraversal(struct Node* node) {
    if (node == NULL) {
        return;
    }
printf("%d ", node->data);
preorderTraversal(node->left);
preorderTraversal(node->right);
}
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
    return newNode;
}


int main() {
    struct Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(5);
    root->right->right = createNode(7);
printf("Pre Order Traversal: ");
preorderTraversal(root);
    return 0;
}

Output:

The output of this code is: Pre Order Traversal: 4 2 1 3 6 5 7

Post Order Traversal

Post order traversal is another method of visiting each node in a tree data structure. In this method, we first traverse the left child of the root node, then the right child, and finally, we visit the root node. This is why it is called post order, as the root node is visited after its child nodes.

The algorithm of post order traversal is as follows:

• Check the root node whether it is NULL or not.
• Traverse the left child of the root node recursively.
• Traverse the right child of the root node recursively.
• Visit the root node.

Let's understand post order traversal with an example.

Suppose a tree is given as:

        4
      /   \
     2     6
    / \   / \
  1   3 5   7

Post-order traversal would direct us to begin at the leftmost leaf node, i.e., 1. Then we would move to the right child of 2, which is 3. After that, we would visit 2, as it has no other child nodes. Then we would move to the left child of 6, i.e., 5, and then to its right child, i.e., 7. After that, we would visit the root node, i.e., 4.

Hence the output of this post-order traversal is: 1 3 2 5 7 6 4

Let's see the code implementation of postorder traversal in C.

Example:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
void postorderTraversal(struct Node* node) {
    if (node == NULL) {
        return;
    }
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%d ", node->data);
}
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
    return newNode;
}


int main() {
    struct Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(5);
    root->right->right = createNode(7);
printf("Post-order Traversal: ");
postorderTraversal(root);
    return 0;
}

Output:

The Output of this code is: Post-order Traversal: 1 3 2 5 7 6 4

Depth First Search

The popular graph traversal algorithm known as DepthFirst Search (DFS) is used to examine every node and edge in a graph. The DFS algorithm begins at a starting node and traverses every node in the graph as thoroughly as it can before going back to other nodes.

The DepthFirst Search in the graph algorithm is as follows:

• Select a beginning node, indicate it has been visited, and then include it in the stack.
• Pop a node from the stack while it still contains vertices to get its neighbouring vertices.
• If a node has not been visited yet for any of its neighbours, mark it as visited, add it to the stack, and carry on with the loop.
• If all of the nearby nodes have been seen, go return to the first one and carry on with the loop.

Let’s understand this depth first search with an example of a graph.

Let’s take an undirected graph of 5 nodes.

 0 – 3

 |  \

 1 – 2 – 4

Here we start the DepthFirst Search approach from node 0 by adding it to the Visited list and adding all of its nearby vertices to the stack. In this case, I underline the nodes which are visited.

0 – 3

 |  \

 1 – 2 – 4

Next, we go to the nearby nodes of element 0, which are 1, 2, 3 and visit node 1.

0 – 3

 |  \

1 – 2 – 4

From node 1, we go to its adjacent node, i.e., 0 and 2, but 0 has already been seen, so we visit 2.

0 – 3

 |  \

1 – 2 – 4

Node 2 has an unvisited neighbouring node in 4, so we visit it and move it to the top of the stack.

0 – 3

 |  \

1 – 2 – 4

At last, we visited node 3. After this node, no nodes remain to be visited, so our DFS algorithm stops here.

0 – 3

 |  \

1 – 2 – 4

So, the Traversal order of this graph using Depth First Search is: 0 1 2 4 3

Now, it is clear how a Depth First Search Algorithm works.

Let's see the code implementation of the Depth FirstSearch traversal of this graph in C++.

Example:

#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
    int num_vertices;
    vector<vector<int>>adj_list;


public:
Graph(int num_vertices) {
        this->num_vertices = num_vertices;
adj_list.resize(num_vertices);
    }


    void addEdge(int src, int dest) {
adj_list[src].push_back(dest);
adj_list[dest].push_back(src);
    }


    void DFS(int start_node, vector<bool>& visited) {
        visited[start_node] = true;
cout<<start_node<< " ";


        for (int i = 0; i<adj_list[start_node].size(); i++) {
            int neighbor = adj_list[start_node][i];
            if (!visited[neighbor]) {
DFS(neighbor, visited);
            }
        }
    }


    void DFS(int start_node) {
        vector<bool>visited(num_vertices, false);
DFS(start_node, visited);
    }


    void printGraph() {
        for (int i = 0; i<num_vertices; i++) {
cout<< "Adjacency list of node " << i << ": ";
            for (int j = 0; j <adj_list[i].size(); j++) {
cout<<adj_list[i][j] << " -> ";
            }
cout<< "NULL" <<endl;
        }
    }
};


int main() {
    Graph graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(2, 4);
graph.printGraph();


cout<< "DepthFirst Search traversal starting from node 0: ";
graph.DFS(0);
cout<<endl;
    return 0;
}

Output:

Adjacency list of node 0: 1 -> 2 -> 3 -> NULL
Adjacency list of node 1: 0 -> 2 -> NULL
Adjacency list of node 2: 0 -> 1 -> 4 -> NULL
Adjacency list of node 3: 0 -> NULL
Adjacency list of node 4: 2 -> NULL
DepthFirst Search traversal starting from node 0: 0 1 2 4 3

Breadth First Search

We have discussed the Depth First Search. Let’s talk about another important traversal algorithm of a graph, i.e., the Breadth First Search. It is a traversal technique which traverses every node according to the layers of a tree or graph. However, unlike Depth First Search, Breadth First Search traverses the graph in layers, starting from the initial node and then moving to all its neighbours before visiting their neighbours. The BFS algorithm can be implemented using a queue data structure, which helps maintain the order in which vertices are visited.

Following is the breadth first search algorithm for a graph:

• Choose a starting node, indicate it has been visited, and add it to the queue.
• Pop a node from the queue, mark it as visited, and then visit all its neighbour nodes.
• For each unvisited neighbour, mark it as visited, add it to the queue, and move on to the next node in the queue.
• Repeat steps 2-3 until the queue becomes empty.

Let's consider the same graph used in the Depth First Search example and implement the BreadthFirst Search algorithm to traverse it. Here, we start from node 0,mark it and add its adjacent nodes to a queue. In this case, I underline the nodes that are visited.

0 – 3

 |  \

 1 – 2 – 4

Next, 1 is visited, and 2 and 3 are in the queue.

0 – 3

 |  \

1 – 2 – 4

Next, node 2 is marked as visited, and we add the adjacent node of node 2 to the queue. So, the queue becomes 3 and 4.

0 – 3

 |  \

1 – 2 – 4

From node 2, from the queue, the next node is to be marked in 3, and node 4 in remaining in the queue.

0 – 3

 |  \

1 – 2 – 4

At last, form node 4 is visited from the queue, and our traversal is completed as no other nodes remain.

0 – 3

 |  \

1 – 2 – 4

Therefore, the traversal order of this graph using BreadthFirst Search is: 0 1 2 3 4.

Now, let's see the code implementation of the BreadthFirst Search algorithm in C++.

Example:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;


class Graph {
private:
    int num_nodes;
    vector<vector<int>>adj_list;


public:
Graph(int num_nodes) {
        this->num_nodes = num_nodes;
adj_list.resize(num_nodes);
    }


    void addEdge(int src, int dest) {
adj_list[src].push_back(dest);
adj_list[dest].push_back(src);
    }


    void BFS(int start_node) {
        vector<bool>visited(num_nodes, false);
        queue<int> q;


        visited[start_node] = true;
q.push(start_node);


        while (!q.empty()) {
            int node = q.front();
cout<< node << " ";
q.pop();


            for (int i = 0; i<adj_list[node].size(); i++) {
                int neighbor = adj_list[node][i];
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
q.push(neighbor);
                }
            }
        }
    }


    void printGraph() {
        for (int i = 0; i<num_nodes; i++) {
cout<< "Adjacency list of node " <<i<< ": ";
            for (int j = 0; j <adj_list[i].size(); j++) {
cout<<adj_list[i][j] << " -> ";
            }
cout<< "NULL" <<endl;
        }
    }
};


int main() {
    Graph graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(2, 4);
graph.printGraph();


cout<< "BreadthFirst Search traversal starting from node 0: ";
graph.BFS(0);
cout<<endl;


    return 0;
}

Output:

Adjacency list of node 0: 1 -> 2 -> 3 -> NULL
Adjacency list of node 1: 0 -> 2 -> NULL
Adjacency list of node 2: 0 -> 1 -> 4 -> NULL
Adjacency list of node 3: 0 -> NULL
Adjacency list of node 4: 2 -> NULL
BreadthFirst Search traversal starting from node 0: 0 1 2 3 4 

In the domain of graph theory, there exist two essential techniques commonly utilized when traversing network data structures: DFS (Depth First Search) and BFS (Breadth First Search). While these approaches are aimed at exploring graphs, their mechanisms vary widely and provide diverse benefits. When scanning through a graph structure, DFS offers unparalleled support because its methodology involves concentrating on one path or branch exclusively until necessary termination criteria come into play or the target node has been reached. The retrieval technique allowing for this multifaceted garden-path method is accomplished using stacks. DFS, as a graph traversal algorithm, serves multiple purposes, such as topologically sorting a graph, establishing a path between two nodes or identifying cycles in a network.

On the other hand, the breadth-first search procedure visits all of the nodes at the current depth level before moving on to the next level. A queue data structure is utilized to implement this strategy which helps to move through levels effectively. Consequently, it is also useful for determining various characteristics of graphs, such as diameter calculation, shortest path determination or finding related components. In computer science and mathematics, DFS and BFS hold immense importance owing to their versatility and numerous applications.

With the capability of serving as crucial tools in natural language processing, social networks, computer networks, and artificial intelligence areas, they have become quintessential algorithms for graph problems.

Conclusion

We can say that traversal techniques are essential for accessing, searching, and processing data in various data structures such as arrays, lists, trees, or graphs. Different traversal strategies, such as Depth First Search and Breadth First Search, offer advantages and disadvantages depending on the specific goals of the problem. By mastering traversal techniques, developers can efficiently navigate through complex data structures and solve a wide range of computational problems.