What is Traversing in Data Structure?

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

Linked List Traversal Example

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!