A tree is a hierarchical data structure made up of nodes and connected by the edges. HTML and XML are two markup languages. Also, you can learn what Hyper Text Markup Language is and how it can be used. Both HTML and XML use a tree structure, with a root that includes child branches, which in turn may have their own child branches, and so on. Tree traversal in a data structure is a type of graph traversal in computer science. Interested in learning more about data structures? Here you will find information about data structures, their types, applications and many more.
What is Tree Traversal in Data Structure?
Tree traversal in a data structure is a type of graph traversal in the data structure that refers to the process of visiting, verifying, and updating each node in a tree data structure just once. The order in which you examine the nodes of the tree is used to classify these traversals.
Next, you will see some data structures which are used in the tree traversal.
Data Structure Used for Implementing Tree Traversal
Iterating over all nodes is required when traversing a tree data structure. Because there is more than one possible next node from a given node because a tree is not a linear data structure, it must postpone specific nodes must and store them in some fashion for later visits, assuming sequential execution.
In a tree data structure, there are primarily two data structures that are used for traversal:

Stack Data Structure
This first data structure is a stack, which is a container for added and removed items according to the lastinfirstout (LIFO) principle.

Queue Data Structure
Now let's look at the basic operations and queue in data structure and discover what they all mean. The firstin, firstout (FIFO) concept governs how you add and withdraw objects in linear data sets from a queue.
You will cover the varieties of tree traversal in the data structure next in this data structure tutorial.
Types of Tree Traversal in Data Structure
You can perform tree traversal in the data structure in numerous ways, unlike arrays, linked lists, and other linear data structures, which are canonically traversed in linear order. You can walk through them in either a depthfirst search or a breadthfirst search. Inorder, preorder, and postorder are the three most frequent ways to go over them in depthfirst.
Beyond these fundamental traversals, more complex or hybrid techniques, such as depthlimited searches, such as iterative deepening depthfirst search, are feasible.
Depth First Search
The depthfirst search (DFS) is a method of traversing or searching data structures composed of trees or graphs.
To get to the recursion, go down one level. If the tree isn't empty, perform the three procedures below in a specific order:
Left: Recursively traversed left subtree
Right: Recursively traversed right subtree
Node: Traverse the root node
Three orders execute tree traversal under this depthfirst search algorithm.
PreOrder Traversal ( RootLeftRight)
 Traverse root node
 Traverse left subtree
 Traverse right subtree
Uses of preorder traversal
To duplicate the tree, you need to use preorder traversal. Preorder traversal is used to obtain a prefix expression from an expression tree.
InOrder Traversal ( LeftRootRight)
 Traverse left subtree
 Traverse root node
 Traverse right subtree
Uses of inorder traversal
Inorder traversal gives nodes in nondecreasing order in binary search trees or BST. A version of Inorder traversal with Inorder traversal reverse can access BST nodes in nonincreasing order.
PostOrder Traversal ( LeftRightRoot)
 Traverse left subtree
 Tereveser right subtree
 Traverse root node
Uses of inorder traversal
You can delete the tree using postorder traversal. The postfix expression of tree data structure can also be obtained using postorder traversal.
Depth First Search or Level Order Traversal
BFS (BreadthFirst Search) is a vertexbased method for determining the shortest path in a graph. It employs a queue data structure, where first in, it follows first out. In BFS, it visits one vertex and marks it at the time, after which it sees and queues its neighbors.
After understanding the types of tree traversal in data structures, you will now examine how to implement tree traversal in data structures.
Implementations of Tree Traversal in Data Structure
PreOrder Traversal
preorder_traversal(node) if (node == null) return visit(node) preorder_traversal(node.left_subtree) preorder_traversal(node.right_subtree) 
InOrder Traversal
inorder_traversal(node) if (node == null) return inorder_traversal(node.left_subtree) visit(node) inorder_traversal(node.right_subtree) 
InOrder Traversal
postorder_traversal(node) if (node == null) return postorder_traversal(node.left_subtree) postorder_traversal(node.right_subtree) visit(node) 
Code of implementing all three tree traversal in data structure
#include <stdio.h> #include<conio.h> #include <stdlib.h> enum Traversal {Preorder_Traversal, Inorder_Traversal, Postorder_Traversal}; typedef enum Traversal trav; typedef struct Node Node; struct Node { int x; Node* left_node, *right_node; }; Node* create_tree(int data) { //creating tree Node* root = (Node*) malloc (sizeof(Node)); root>left_node= root>right_node = NULL; root>x = data; return root; } Node* create_node(int data) { //creating node Node* node = (Node*) malloc (sizeof(Node)); node>x = data; node>left_node = node>right_node = NULL; return node; } void release_tree(Node* root) { //releasing tree Node* t = root; if (!t) return; release_tree(t>left_node); release_tree(t>right_node); if (!t>left_node && !t>right_node) { free(t); return; } } void displaytree(Traversal trav, Node* root) { if (!root) return; switch(trav) { case (Preorder_Traversal): //preorder traversal printf("%d > ", root>x); displaytree(trav, root>left_node); displaytree(trav, root>right_node); break; case (Inorder_Traversal): //inorder traversal displaytree(trav, root>left_node); printf("%d > ", root>x); displaytree(trav, root>right_node); break; case (Postorder_Traversal): // preorder traversal displaytree(trav, root>left_node); displaytree(trav, root>right_node); printf("%d > ", root>x); break; } } int main() { Node* root = create_tree(5); root>left_node = create_node(10); root>right_node = create_node(15); root>left_node>left_node = create_node(20); root>left_node>right_node = create_node(25); root>right_node>left_node = create_node(30); root>right_node>right_node = create_node(35); printf("Preorder Traversing\n"); displaytree(Preorder_Traversal, root); printf("\n\n"); printf("Inorder Traversing\n"); displaytree(Inorder_Traversal, root); printf("\n\n"); printf("Postorder Traversing\n"); displaytree(Postorder_Traversal, root); release_tree(root); return 0; } 
Output of tree traversal code:
Preorder Traversing 5 > 10 > 20 > 25 > 15 > 30 > 35 > Inorder Traversing 20 > 10 > 25 > 5 > 30 > 15 > 35 > Postorder Traversing 20 > 25 > 10 > 30 > 35 > 15 > 5 > 
Finally, in this tutorial, you will look at various tree traversal applications in data structures.
Applications of Tree Traversal in Data Structure
 To build a prefix expression (Polish notation) from expression trees, utilize preorder traversal: traverse the expression tree in a preorderly manner.
 For e.g. A+B * ( CD) > A +B * CD > +AB * CD > *+ABCD
A prefix notation is known as Polish notation. All operators must come before the two operands they work on in prefix expression notation.
 You can generate a binary tree's postfix representation or reverse Polish notation using postorder traversal.
 For e.g. A+B * ( CD) > A +B * CD > AB+ * CD > AB+CD*
The operators must occur after the corresponding operands in postfix notation, also known as reverse polish notation.
 Because it returns values from the underlying set in order, according to the comparator setting up the binary search tree, it often employs traversal on binary search trees.
You can delete or release a complete binary tree when deleting or freeing nodes and values in the postorder traversal. As a result, it liberates the node once it frees its children.
Advance your career as a MEAN stack developer with the Full Stack Web Developer  MEAN Stack Master's Program. Enroll now!
Next Step
You learned how to do tree traversal in data structures and which data structures you require to implement tree traversal in this lesson. And you also learned about different forms of tree traversal in data structures.
"Graphs in Data Structures" will be your next topic, where you will learn what a graph data structure is and the types of graph data structure. If you want to learn more about data structures and programming languages, go to Simplilearn's Software development course and start learning.
Please feel free to ask any questions you may have about the "tree traversal in data structure" tutorial in the comments section below. We will gladly assist you in resolving your issues as quickly as possible.
Until then, please remain safe and subscribe to the Simplilearn channel.