Updated March 6, 2023
Definition of Tree Traversal in Data
Traversal refers to the process of visiting all the nodes of a tree and perform operations using the same data. Since all the nodes are connected through edges thus are linked randomly visiting any node is off the table. We need to start from the root i.e head node of the tree. Thus there are only three ways
1. Inorder traversal
2. Pre-order Traversal
3. Post-order Traversal
Syntax:
1. Inorder Traversal – Left Child -> Root -> Right Child
2. Pre-Order Traversal – Root -> Left Child -> Right Child
3. Post-Order Traversal – Left Child -> Right Child -> Root
How Tree traversal performs in data structure?
Traversal differs in the order nodes are visited, thus all three traversals have the same complexities. Still, different traversals have different applications. Let’s discuss the algorithms for each type of traversal.
We must remember that every node in a tree represents a separate sub-tree itself.
Inorder Traversal
In this type of traversal, one must first traverse to the leftmost node of the tree by pointing the next pointer to the left child of the node.
While(node->left !=null)
node->next = node->left
Then we can read the data from the node and assign a pointer to the parent of the current node. Then after reading data from the parent node we can start traversing the right subtree in Left -> Root -> right fashion.
Since the root of the node is traversed after left and before right child of the subtree thus is named as in-order traversal means in between the left and right child.
Until all nodes are traversed
Step 1 – Traverse to the leftmost node of the left subtree.
Step 2 – Traverse the root node.
Step 3 – Then traverse the right subtree recursively.
Pre-Order Traversal
In this type of traversal, one must first traverse to the root node of the tree then the left subtree then the right subtree.
Since the root of the node is traversed before the left and right child of the subtree thus is named as pre-order traversal.
Until all nodes are traversed
Step 1 – Read the root node of the tree.
Step 2 – Move to the left child of the tree and read it.
Step 3 – Then check if it has a left child then move to the left child otherwise move to the right child of the node.
Step 4 – Follow Step 1,2 and 3 to further subtree.
Post-Order Traversal
In this type of traversal, one must first traverse to the leftmost node of the tree and then traverse the right subtree of the immediate parent and then traverse the root of the subtree.
Since the root of the node is traversed after the left and right child of the subtree thus is named as post-order traversal.
Until all nodes are traversed –
Step 1 − Recursively traverse left- most child of the left subtree.
Step 2 – Read the node data and then move to the right subtree of the immediate parent and repeat Step 1.
Step 3 – After reading data from the right child read the immediate parent and move to its parent node.
Examples
Consider the below tree having 6 nodes having A as the root node.
Let us apply the three traversal techniques to print all the nodes in the tree and observe the results.
InOrder traversal
Step 1- Check if Node A(root node) has a left child. In this case yes, move to the left child node B.
Step 2- Check if node B has any left child. If yes move to node D.
Step3- Now check again if node D has left the child. In this case no, thus we have reached the left most child of the tree. Print Node D.
Step 4. Print Node B(parent node to D). Then move to the right child of B, Since there is no right child move to node A. print node A.
Step 5 – Move to the right child of A i.e C and check if it has a left child. Then move to left child i.e E. Move to E and check if E has left child.
Step6 – Since there is no left child of E, print E and move to its parent C and print C.
Step 7- now Check if C has a right child i.e F and then check if F has a left child i.e none. Thus print F.
Result – D B A E C F
Pre-Order traversal
Step 1- Visit root node and print A. Then move to the left child B and print B.
Step 2- Check if node B has any left child. If yes move to node D. Print D
Step3-Now check if B has right child otherwise move to right child of A i.e C.
Step 4. Print C. Check if C has left child E. Print E.
Step 5 – Check if E has left the child. Since no left child move to right child of immediate parent C i.e F.
Step6 – Print F.
Result – A B D C E F
Post-Order traversal
Step 1- Recursively traverse to the leftmost child of the tree i.e D
Step 2- Print D. Then check if the right child of immediate parent i.e B. thus prints immediate parent node B.
Step3-Now check if the parent node of B i.e A has the right Child. Move to C then move to the leftmost node in this sub-tree i.e E. print E.
Step 4. Move to the right child of C i.e F and print F. then print C. Then print root node A.
Result –D B E F C A
Conclusion
Traversal of a tree can be done in 3 ways in order, preorder, and postorder depending on the position root of the node is being traversed. Each type of traversal has its own applications. Below are its applications.
In-order traversal – It is used in BST because the value is returned in a particular order and can be used to set the comparator.
Pre-order traversal – This can be used to provide a polish notation or expression of a tree.
Post-order traversal – It is used to generate prefix notation of a binary tree.
Recommended Articles
This is a guide to Tree Traversal in Data Structure. Here we discuss Definition, syntax, How to perform Tree Traversal? examples. You may also have a look at the following articles to learn more –
