Traversing in Data Structure

Introduction

Hello, ninjas! You must have studied different types of data structures when solving a coding problem. This article will explore how to traverse various types of data structures. Traversing in data structures refers to systematically visiting and processing each element or node within a data structure, such as an array, linked list, tree, or graph.

Let's get started!

What is Traversing in Data Structure?

Traversing in Data structure signifies visiting or accessing each element in a data structure systematically. Generally, it is in such a way that each element is at least visited once. It is iterating over all the elements of the data structure.

Now, let's study traversing in data structures of different types.

Importance of Traversing

Traversing in the data structure is a fundamental concepts that means visiting each node or element in data structure. It has its own importance like :

Searching: Traversing each element helps in searching the element you searched for. If traversing is done correctly, one can examine whether the element exists in the data or not.
Sorting: It is the most important need of the data structure. Traversing and comparing the data helps in sorting the data which means comparison between the elements is easy.
Accessibility: Easy accessibility to data is possible by traversing. Performing various computational rules, or modifying or changing any element can be done by traversing.
Graph and Tree Traversal: The complex non-linear data structure makes it important to traverse the nodes and perform operations on data.

What is Array Traversal in Data Structure?

An array is a data structure with continuous memory allocation of elements. For traversing an array, we can iterate over every element continuously. Although, with a particular index, we can access any element of an array. E.g.:-

Let us look at its implementation in C++.

Code

C++

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 4, 5, 2};
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

What is the Traversing of a Linked List?

A linked list is a data structure in which different nodes in the memory are connected through pointers, and each node contains specific data. We can access elements of a linked list node by node, i.e., continuously only. E.g.:-

Let us look at its implementation in C++.

Code

C++

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        data = x;
        next = NULL;
    }
};

void traversal(Node* &head) {
    if (head == NULL) {
        cout << "No elements in linked list" << endl;
        return;
    }
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

int main() {
    Node* head = new Node(1);
    Node* one = new Node(2);
    Node* two = new Node(3);
    Node* three = new Node(4);
    Node* four = new Node(5);
    head->next = one;
    one->next = two;
    two->next = three;
    three->next = four;
    traversal(head);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Stack Traversing Traversal in Data Structure

A stack is a data structure that follows the LIFO(Last In, First Out) technique for the insertion and deletion of data. E.g.:-

For its traversal, we can only access the top element of a stack. Thus, each time we will access the top element and remove it from the stack to access the next element. If required, using recursion, we can retain the original stack pushing back each popped element into it recursively.

Code

C++

#include<iostream>
#include<stack>
using namespace std;

void traversal(stack<int> &s) {
    if (s.empty()) {
        return;
    }
    int c = s.top();
    s.pop();
    cout << c << " ";
    traversal(s);
    s.push(c);
}

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    traversal(s);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

What is Queue Traversal?

A queue is a data structure following the FIFO(First In, First Out) technique for the insertion and deletion of data. E.g.:

We can access the front element of the queue, and we can remove elements from there only. Thus, we will access the front element for traversal and then remove it from the queue. If required, using recursion, we can retain the original queue pushing back each popped element into it recursively.

Let us look at the implementation of the traversal of a queue in C++.

Code

C++

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

void traverse(queue<int> &q) {
    if (q.empty()) {
        return;
    }
    int x = q.front();
    q.pop();
    cout << x << " ";
    q.push(x); // Push the element back onto the queue after printing it
    traverse(q);
}

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    traverse(q);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

What is Binary Tree Traversal?

A tree is a data structure that has parent and child nodes containing no cycle.

A Binary tree is a data structure with two children nodes at most of a parent node.

A Binary Search Tree is a data structure in which, for the current node, the left child node has a value lesser than the current node's value, and the right child node has a value greater than the current node's value.

E.g.:-

Basically, there are four techniques for tree traversal:

Level Order Traversal
Inorder Traversal
Preorder Traversal
Postorder Traversal

Level Order Traversal

In level-order traversal, we iterate the tree level by level. First, we iterate over all the elements of the current level. Then, we move to the next level until we reach the end of the tree.

Let us look at its implementation in C++.

Code

C++

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

class Node {
public:
    int data;
    Node* left;
    Node* right;
    
    Node() {
        data = 0;
        left = NULL;
        right = NULL;
    }
    
    Node(int x) {
        data = x;
        left = NULL;
        right = NULL;
    }
};

Node* insert(Node* root, int val) {
    if (root == NULL) {
        Node* temp = new Node(val);
        return temp;
    }
    if (root->data > val) {
        root->left = insert(root->left, val);
    }
    else {
        root->right = insert(root->right, val);
    }
    return root;
}

void levelorder(Node* root) {
    if (root == NULL) {
        cout << "No elements in the tree" << endl;
        return;
    }
    queue<Node*> q;
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        if (temp == NULL) {
            cout << endl;
            if (!q.empty()) {
                q.push(NULL);
            }
        }
        else {
            cout << temp->data << " ";
            if (temp->left) q.push(temp->left);
            if (temp->right) q.push(temp->right);
        }
    }
}

int main() {
    Node* root = new Node(1);
    root = insert(root, 2);
    root = insert(root, 3);
    root = insert(root, 0);
    
    levelorder(root);
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Inorder Traversal

In inorder traversal, we iterate the tree in the following order:-

The Left part of the tree.
The Current node of the tree.
The Right part of the tree.

In a BST(Binary Search Tree), the inorder traversal prints the elements of the tree in ascending order.

Let us look at its implementation in C++.

Code

C++

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

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node() {
        data = 0;
        left = NULL;
        right = NULL;
    }
    Node(int x) {
        data = x;
        left = NULL;
        right = NULL;
    }
};

Node* insert(Node* root, int val) {
    if (root == NULL) {
        Node* temp = new Node(val);
        return temp;
    }
    if (root->data > val) {
        root->left = insert(root->left, val);
    }
    else {
        root->right = insert(root->right, val);
    }
    return root;
}

void inorder(Node* root) {
    if (root == NULL)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = new Node(1);
    root = insert(root, 2);
    root = insert(root, 3);
    root = insert(root, 0);
    inorder(root);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Preorder Traversal

In preorder traversal, we iterate the tree in the following order:-

The Current node of the tree.
The Left part of the tree.
The Right part of the tree.

Let us look at its implementation in C++.

Code

C++

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

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node() {
        data = 0;
        left = NULL;
        right = NULL;
    }
    Node(int x) {
        data = x;
        left = NULL;
        right = NULL;
    }
};

Node* insert(Node* root, int val) {
    if (root == NULL) {
        Node* temp = new Node(val);
        return temp;
    }
    if (root->data > val) {
        root->left = insert(root->left, val);
    }
    else {
        root->right = insert(root->right, val);
    }
    return root;
}

void preorder(Node* root) {
    if (root == NULL)
        return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

int main() {
    Node* root = new Node(1);
    root = insert(root, 2);
    root = insert(root, 3);
    root = insert(root, 0);
    preorder(root);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Postorder Traversal

In postorder traversal, we iterate the tree in the following order:-

The Left part of the tree.
The Right part of the tree.
The Current node of the tree.

Let us look at its implementation in C++.

Code

C++

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

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node() {
        data = 0;
        left = NULL;
        right = NULL;
    }
    Node(int x) {
        data = x;
        left = NULL;
        right = NULL;
    }
};

Node* insert(Node* root, int val) {
    if (root == NULL) {
        Node* temp = new Node(val);
        return temp;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    }
    else if (val > root->data) { // Use else if here
        root->right = insert(root->right, val);
    }
    return root;
}

void postorder(Node* root) {
    if (root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

int main() {
    Node* root = new Node(1);
    root = insert(root, 2);
    root = insert(root, 3);
    root = insert(root, 0);
    postorder(root);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Also see, Rabin Karp Algorithm And Application of Graph in Data Structure

Graph Traversal in Data Structure

A graph is a data structure that has nodes containing data connected through edges.
It can be directed if the edge between two nodes has a specific direction. It can also be undirected if the edge between two nodes has no specified direction. It is bidirectional.
A graph is weighted if the edge between two nodes has a specific value or cost. It is unweighted if the edge between two nodes has no particular value or cost.

E.g.:

Traversal in a graph has two techniques:

BFS Traversal
DFS Traversal

BFS Traversal

It stands for Breadth First Search. In this, we iterate over all the elements of a level and then move on to the next level.

Steps to follow:

Maintain three data structures, a visited array, an answer array, and a queue.
Add the starting node to the visited array, and add the node itself and all its adjacent nodes into the queue.
Using the FIFO concept of the queue, remove the front element of the queue. Store it in the answer. And, for all its adjacent nodes which have not been visited before, push them into the queue and mark them visited.
Repeat step three until the queue is empty.

Let us look at its implementation in C++.

Code

C++

#include<iostream>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;

void bfs(unordered_map<int, set<int>>& adj, unordered_map<int, bool>& visited, vector<int>& ans, int node) {
    queue<int> q;
    q.push(node);
    visited[node] = true;
    while (!q.empty()) {
        int temp = q.front();
        q.pop();
        ans.push_back(temp);
        for (auto i : adj[temp]) {
            if (visited[i] == false) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    unordered_map<int, set<int>> adj;
    adj[0].insert(1);
    adj[1].insert(0);
    adj[3].insert(0);
    adj[0].insert(3);
    adj[1].insert(2);
    adj[2].insert(1);
    adj[2].insert(3);
    adj[3].insert(2);
    unordered_map<int, bool> visited;
    vector<int> ans;
    bfs(adj, visited, ans, 0);
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

DFS Traversal

It stands for Depth-First-Search. In this, we iterate completely over the current node and its branch until we reach its end. And then, we move on to the next branch.

Steps to follow:

Maintain a visited array and a stack
Start with the starting node and push that node into the stack.
Afterward, push a node that has not been visited before and is adjacent to the node at the top of the stack into the stack, and mark it as visited.
Repeat steps 3 and 4 until all the nodes are visited. If no node is left, pop a node from the stack.
Repeat these steps until the stack is empty.

For the above example, it can be viewed as below.

Let's take a look at its implementation in C++.

Code

C++

#include<iostream>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;

void dfs(vector<int> &temp, unordered_map<int, bool> &visited,
         unordered_map<int, set<int>> &adj, int node) {
    temp.push_back(node);
    visited[node] = true;
    for (auto i : adj[node]) {
        if (visited[i] == false) {
            dfs(temp, visited, adj, i);
        }
    }
}

int main() {
    unordered_map<int, set<int>> adj;
    adj[0].insert(1);
    adj[1].insert(0);
    adj[3].insert(0);
    adj[0].insert(3);
    adj[1].insert(2);
    adj[2].insert(1);
    adj[2].insert(3);
    adj[3].insert(2);
    unordered_map<int, bool> visited;
    vector<int> temp;
    dfs(temp, visited, adj, 0);
    for (int i = 0; i < temp.size(); i++) {
        cout << temp[i] << " ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Frequently Asked Questions

What is traversing in data structure with example?

What is traversing array in data structure?

Traversing array data structure is visiting each element in an array. This helps in easy understanding and analyzing the data. This process typically involves iterating each element of an array, starting from the first element and going till the last element.

What is traversing technique?

Traversing is a fundamental concept that means visiting each node or element in the data structure. There are various traversing techniques that is used in computer programming depending on the data structure used. The most common traversing techniques are sequential traversal, depth-first traversal, inorder postorder and preorder traversal, and many more.

What is traversing a tree structure?

Traversing a tree structure is systematically traversing each node of a tree. It involves various techniques and methods such as inorder traversal, postorder traversal and preorder traversal.

What are the 3 ways of traversing a binary tree?

The 3 common ways to traverse a binary tree are inorder, preorder, and postorder traversal. All three provide different unique way to traverse the binary tree depending upon the requirement and application.

Conclusion

Traversing in data structures is an important aspect when dealing with different data structures. In this article, we studied traversing in data structures by first understanding its meaning and then learning about different techniques of traversing in data structures of various types.

We have more for you. Give a read to the following articles to learn more about Traversals:

To learn more about Data Structures and Algorithms, you can enroll in our DSA in C++ Course.

Happy Coding!