What Is Traversing in Data Structure With Example?

In data structures, traversing refers to the process of visiting each element in a data structure. It allows you to access and manipulate the data stored within the structure. Traversing is an essential operation as it enables you to perform various tasks, such as searching for specific elements, modifying values, or analyzing the data.

Types of Traversing

There are two commonly used methods for traversing data structures:

• Sequential Traversal: Also known as linear traversal, sequential traversal visits each element in a sequential manner starting from the first element and moving towards the last. This method is typically used with linear data structures like arrays and linked lists.
• Hierarchical Traversal: Hierarchical traversal is used with hierarchical or tree-like data structures such as trees and graphs. It involves visiting each node in a hierarchical manner, starting from a specific root node and moving through its children or neighboring nodes.

Example of Sequential Traversal

Let’s consider an example of sequential traversal using an array. Suppose we have an array named numbers, which contains five integers: [10, 20, 30, 40, 50]. To traverse this array sequentially, we can use a loop that iterates through each element:

// Declare and initialize the array
int[] numbers = {10, 20, 30, 40, 50};

// Perform sequential traversal using a loop
for (int i = 0; i < numbers.length; i++) {
    System.out.println(numbers[i]);
}

The above code snippet demonstrates how we can traverse an array sequentially using a for loop. It starts from the first element (index 0) and continues until it reaches the last element (index 4). During each iteration, the value of the current element is printed.

Example of Hierarchical Traversal

Let's now consider an example of hierarchical traversal using a binary tree. Suppose we have a binary tree with the following structure:

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

To traverse this binary tree hierarchically, we can use a technique called breadth-first traversal. It visits nodes at each level before moving on to the next level. Here's how we can perform hierarchical traversal on this binary tree:

// Define the BinaryTreeNode class with value and left/right child references
class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode(int value) {
        this.value = value;
    }
}

// Perform hierarchical traversal using a queue
void breadthFirstTraversal(BinaryTreeNode root) {
    if (root == null)
        return;

    Queue queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        BinaryTreeNode currentNode = queue.poll();
        System.println(currentNode.value);

        if (currentNode.left != null)
            queue.add(currentNode.left);

        if (currentNode.right != null)
            queue.right);
    }
}

// Create an instance of the binary tree and perform hierarchical traversal
BinaryTreeNode root = new BinaryTreeNode(1);
root.left = new BinaryTreeNode(2);
root.right = new BinaryTreeNode(3);
root.left.left = new BinaryTreeNode(4);
root.right = new BinaryTreeNode(5);
root.right.left = new BinaryTreeNode(6);
root.right = new BinaryTreeNode(7);

breadthFirstTraversal(root);

The above code snippet demonstrates how we can traverse a binary tree hierarchically using a queue. It starts from the root node (value 1) and visits its left and right children (values 2 and 3). Then it moves on to the next level, visiting nodes 4, 5, 6, and 7.

Conclusion

Traversing is a fundamental operation in data structures that allows us to access and manipulate the data stored within them. Sequential traversal is used with linear data structures like arrays and linked lists, while hierarchical traversal is used with hierarchical or tree-like structures such as trees and graphs. By understanding and implementing traversing techniques, you can effectively work with various data structures in your programs.