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 that 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)**

- Traverse the left subtree of the tree, call Inorder(left-subtree)
- Visit the root of the tree.
- 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)**

- Visit the root of the tree.
- Traverse the left subtree of the tree, call Preorder(left-subtree)
- 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)**

- Traverse the left subtree of the tree, call Postorder(left-subtree)
- Traverse the right subtree of the tree, call Postorder(right-subtree)
- 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**

*// C++ program to display in-order, post-order, pre-order traversal of tree*
#include <iostream>
using namespace std;
*/* A binary tree node has data stored as value, pointer to left child
**and right child */*
struct Node {
int value;
struct Node *left, *right;
};
*//function for creating new tree node*
Node* createNode(int value){
Node* t = new Node;
t->value = value;
t->left = t->right = NULL;
return t;
}
*/* printing postorder traversal of binary tree */*
void postorder(struct Node* root){
if (root == NULL)
return;
*// first traverse left subtree*
postorder(root->left);
*// then traverse right subtree*
postorder(root->right);
*// now visit root node*
cout << root->value << " ";
}
*/* inorder traversal of the binary tree*/*
void inorder(struct Node* root){
if (root == NULL)
return;
*/* first visit left child */*
inorder(root->left);
*/* print root data */*
cout << root->value << " ";
*/* at last recur over right subtree */*
inorder(root->right);
}
*/* Preorder traversal of the binary tree*/*
void preorder(struct Node * root){
if (root == NULL)
return;
*/* display node value */*
cout << root->value << " ";
*/* then traverse left subtree */*
preorder(root->left);
*/* now traverse right subtree */*
preorder(root->right);
}
int main(){
struct Node* n = createNode(1);
n->left = createNode(2);
n->right = createNode(3);
n->left->left = createNode(4);
n->left->right = createNode(5);
cout << "\nPreorder traversal of tree: \n";
preorder(n);
cout << "\nInorder traversal of tree: \n";
inorder(n);
cout << "\nPostorder traversal of tree: \n";
postorder(n);
return 0;
}

**Output**

```
Preorder traversal of binary tree :
1 2 4 5 3
Inorder traversal of binary tree :
4 2 5 1 3
Postorder traversal of binary tree :
4 5 2 3 1
```

**Java Implementation**

*// Java program for different tree traversals*
*/* Class containing left and right child of current
**node and key value*/*
class Node {
int data;
Node left, right;
public Node(int item){
data = item;
left = right = null;
}
}
class Tree {
*// Root of Binary Tree*
Node root;
Tree() { root = null; }
*/* print postorder traversal of given tree. */*
void postorder(Node root){
if (root == null)
return;
*// first traverse left subtree*
postorder(root.left);
*// then traverse right subtree*
postorder(root.right);
*// at last print root value*
System.out.print(root.data + " ");
}
*/* print inorder traversal of binary tree*/*
void inorder(Node root){
if (root == null)
return;
*/* first trvarese left subtree */*
inorder(root.left);
*/* then print the data of node */*
System.out.print(root.data + " ");
*/* at last trvaerse right subtree */*
inorder(root.right);
}
*/* printing preorder traversal of binary tree*/*
void preorder(Node root){
if (root == null)
return;
*/* print node value */*
System.out.print(root.data + " ");
*/* then traverse left subtree */*
preorder(root.left);
*/* now traverse right subtree */*
preorder(root.right);
}
*// calling functions for traversals of binary tree*
void postorder() {
postorder(root);
}
void inorder() {
inorder(root);
}
void preorder() {
preorder(root);
}
public static void main(String[] args){
Tree t = new Tree();
t.root = new Node(1);
t.root.left = new Node(2);
t.root.right = new Node(3);
t.root.left.left = new Node(4);
t.root.left.right = new Node(5);
System.out.println(
"Preorder traversal of tree : ");
t.preorder();
System.out.println(
"\nInorder traversal of tree : ");
t.inorder();
System.out.println(
"\nPostorder traversal of tree : ");
t.postorder();
}
}

**Output**

```
Preorder traversal of binary tree :
1 2 4 5 3
Inorder traversal of binary tree :
4 2 5 1 3
Postorder traversal of binary tree :
4 5 2 3 1
```

**Python Implementation**

*# Python program for tree traversals*
*# A class that represents an individual node in a*
*# Binary Tree*
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.data = key
*# printing inorder tree traversal*
def inorder(node):
if node:
*# First traverse left subtree*
inorder(node.left)
*# then print the node data*
print(node.data),
*# now traverse right subtree*
inorder(node.right)
*# postorder tree traversal of binary tree*
def postorder(node):
if node:
*# traverse left subtree*
postorder(node.left)
*# recur on the right child*
postorder(node.right)
*# print node value*
print(node.data),
*# A function to do preorder tree traversal*
def preorder(node ):
if node:
*# print node value*
print(node.data),
*# recur on left child*
preorder(node .left)
*# at last recur on right child*
preorder(node .right)
*# Driver code*
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Preorder traversal of binary tree :")
preorder(root)
print("\nInorder traversal of binary tree :")
inorder(root)
print("\nPostorder traversal of binary tree :")
postorder(root)

**Output**

```
Preorder traversal of binary tree :
1 2 4 5 3
Inorder traversal of binary tree :
4 2 5 1 3
Postorder traversal of binary tree :
4 5 2 3 1
```

## 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!**

## 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.