{"id":84214,"date":"2021-09-20T09:00:23","date_gmt":"2021-09-20T03:30:23","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=84214"},"modified":"2021-09-20T09:00:23","modified_gmt":"2021-09-20T03:30:23","slug":"tree-traversal-in-data-structure","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/tree-traversal-in-data-structure\/","title":{"rendered":"Tree Traversal in Data Structure"},"content":{"rendered":"

Tree traversal means visiting each node of the tree. The tree is a non-linear data structure, and therefore its traversal is different from other linear data structures. There is only one way to visit each node\/element in linear data structures, i.e. starting from the first value and traversing in a linear order. However, in tree data structures, there are multiple ways to traverse it.<\/p>\n

Types of Tree Traversal:<\/h3>\n

Broadly, tree traversal is classified into two categories: Level order or breadth-first traversal and depth-first traversal. The depth-first traversal further has 3 different categories that we are going to study in detail.<\/p>\n

Level Order Traversal:<\/h3>\n

In a level order traversal, the nodes are covered in a level-wise manner from left to right. We can implement a level order traversal with the help of a queue data structure.<\/p>\n

For example, the following diagram depicts the order of traversing the nodes of the tree.<\/p>\n

\"Traversing<\/a><\/p>\n

Here, the level order traversal will print the nodes in the following order: 10, 20, 30, 40, 50, 60, 70.<\/p>\n

Depth First Traversal:<\/h3>\n

In depth-first traversal, we go in one direction up to the bottom first and then come back and go to the other direction. There are three types of depth-first traversals. These are:<\/p>\n

1. Preorder traversal<\/p>\n

2. Inorder traversal<\/p>\n

3. Postorder traversal<\/p>\n

A binary tree is a recursive data structure. Also, each binary tree has 3 parts: a root node, a left subtree and a right subtree. These left and right subtrees are also trees in themselves and thus, again further described recursively.<\/p>\n

\"subtree<\/a><\/p>\n

A tree comprises multiple nodes. The structure of one node is:<\/p>\n

struct Node {\n    int key;\n    struct Node* left;\n    struct Node* right;\n}\n<\/pre>\n
Thus, each node has 3 parts: A data item or key, a pointer to the left child and a pointer to the right child.<\/p>\n
Preorder Traversal:<\/h3>\n
In a preorder traversal, we process\/visit the root node first. Then we traverse the left subtree in a preorder manner. Finally, we visit the right subtree again in a preorder manner.<\/p>\n
For example, consider the following tree:<\/p>\n
\"Preorder<\/a><\/p>\n
Here, the root node is A. All the nodes on the left of A are a part of the left subtree whereas all the nodes on the right of A are a part of the right subtree. Thus, according to preorder traversal, we will first visit the root node, so A will print first and then move to the left subtree.<\/p>\n
B is the root node for the left subtree. So B will print next and we will visit the left and right nodes of B. In this manner, we will traverse the whole left subtree and then move to the right subtree. Thus, the order of visiting the nodes will be: A\u2192B\u2192C\u2192D\u2192E\u2192F\u2192G\u2192H\u2192I.<\/p>\n
Algorithm for Preorder Traversal:<\/h4>\n
for all nodes of the tree:
\nStep 1: Visit the root node.
\nStep 2: Traverse left subtree recursively.
\nStep 3: Traverse right subtree recursively.<\/p>\n
Pseudo-code for Preorder Traversal:<\/h4>\n
void Preorder(struct node* ptr)\n{\n    if(ptr != NULL)\n    {\n        printf(\"%d\", ptr->data);\n        Preorder(ptr->left);\n        Preorder(ptr->right);\n    }\n}\n<\/pre>\n
Uses of Preorder Traversal:<\/h4>\n