# What is Traversing in Data Structure?

Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Topics Covered

## Overview

Traversing in the data structure is a very important operation that can be performed on any data structure. Traversing in Data Structure means systematically visiting every element of it. Traversing is a process in which each element of a data structure is accessed. Accessing an element of data structure means visiting every element at least once. Traversing is performed to display every element of data structure or to perform any operation on its element. Traversing is also known as iterating over the data structure.

## Takeaways

Traversing operation is used to access elements of data structure or to perform some operation on elements.

## What is the Traversal of a Binary Tree?

A binary tree is a data structure in which data is stored in a hierarchical form. Traversal of the binary tree means visiting every node of the tree. The process of accessing the nodes of a tree in some order is called a traversal of a binary tree. Any process for visiting all of the nodes is called a traversal.

## What is the Traversing of a Linked List?

A linked list is a data structure which we will traverse from the head node to the last node of the list. Traversing a linked list means visiting every node of the linked list to perform some operation on the nodes.

## What is Traversal Order?

Unlike linear data structures(Array, Queues, Linked List, Queues, etc.) that have only one way to traverse them but the tree data structure can be traversed in multiple ways.

The tree can be traversed in three ways:

### In-order Traversal

In inorder to traversal of the binary tree,

• Firstly left subtree is visited
• Then the root is visited
• The right subtree is visited.

Above 3 steps are recursively performed.

An in-order traversal of the Binary Search Tree gives us the ascending order of values stored in the tree.

### Pre-order Traversal

In pre-order traversal of a binary tree,

• Firstly root is visited
• Then the left subtree is visited
• Then finally the right subtree is visited.

Above 3 steps are recursively performed.

### Post-order Traversal

In post-order traversal of the binary tree root node is visited at the last. In this

• Firstly left subtree is visited
• Then the right subtree is visited.
• And at last, the root is visited.

Above 3 steps are recursively performed.

## Binary Tree Traversal Techniques

Traversing a binary tree means accessing every node of a tree.

The Tree can be traversed in three ways:

### In-order Traversal

Algorithm

Algorithm Inorder(tree)

1. Traverse the left subtree of the tree, call Inorder(left-subtree)
2. Visit the root of the tree.
3. Traverse the right subtree of the tree, call Inorder(right-subtree)

Example

Below is an image to show an example of the inorder traversal

An in-order traversal of the above example is: 4 2 5 1 3

### Pre-order Traversal

Algorithm Algorithm Preorder(tree)

1. Visit the root of the tree.
2. Traverse the left subtree of the tree, call Preorder(left-subtree)
3. Traverse the right subtree of the tree, call Preorder(right-subtree)

Example

Below is an image to show an example of the preorder traversal

Pre-order traversal of the above example is: 1 2 4 5 3

### Post-order Traversal

Algorithm

Algorithm Postorder(tree)

1. Traverse the left subtree of the tree, call Postorder(left-subtree)
2. Traverse the right subtree of the tree, call Postorder(right-subtree)
3. Visit the root of the tree.

Example

Below is an image to show an example of the postorder traversal

Post-order traversal of the above example is: 4 5 2 3 1

## What are Tree Traversal Methods?

### Traversal Implementation

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

## Examples for Traversing in the Data Structure

### Array Traversal Example

Below is an image to show an example of the array traversal

Traversal of the above array is 1,2,3,4,5,6

Below is an image to show an example of the linked list traversal

Traversal of the above-Linked List is 1,2,3,4,5,6

## Learn about Graph Traversal in Data Structure

Let us take a recap of Graph Traversal

In graph traversal, every node of the graph is visited at least once. Two techniques are used for graph traversal, i.e. Depth First Search and Breadth-First Search.

Boost your C++ proficiency with expertly designed Data Structures in C++ Course by Scaler Topics. Get started now!

## Conclusion

• Traversing a data structure is a very important operation that can be performed on data structures like an array, linked list, tree, graph, etc.
• Traversing means accessing each element of data structure at least once.
• Linked List traversal means accessing all the elements of the list starting from the head node to the last node.
• Traversing a tree and graph means visiting every node at least once.
• In-tree data structure, we have three types of traversal: In-order traversal, Pre-order traversal, and Post-order traversal.
• In the graph, we have Depth First Search and Breadth-First Search for traversing.