EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial Tree Traversal in Data Structure
 

Tree Traversal in Data Structure

Updated March 6, 2023

Tree Traversal in Data Structure

 

 

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

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

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.

Tree Traversal in Data Structure 1

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.

root mode

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 –

  1. Heap Data Structure
  2. Hashing in Data Structure
  3. Stack in Data Structure
  4. B Tree in Data Structure

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW