What is the Tree Traversal in DSA?
Tree Traversal in DSA involving the process of visiting all nodes in a tree Data Structure. It is essential for various types of operations like, searching, sorting and manipulating series data. We have Four Methods of Tree Traversal in DSA.
1. Pre Order Traversal
In The Pre Order Traversal, the root node is processed before its child nodes. This method is useful when you need to create a copy of the tree or evaluate expressions represented in tree form. This visits the node in the following order,
- Visit the Root
- Traverse the Left Subtree
- Traverse the Right Subtree
2. In Order Traversal
In Order Traversal, the left subtree is processed first, followed by the root, and then the right subtree. This Method is widely used in Binary Search tree (BST) as it retrieves nodes in accessing order. It visits the nodes in the following order.
- Traverse the Left Subtree
- Visit the Root
- Traverse the Right Subtree
3. Post Order Traversal
In Post Order Traversal, the root node is processed after its child nodes. This method is useful for deleting trees or evaluating postfix expressions. It visits the nodes in the following order.
- Traverse the Left Subtree
- Traverse the Right Subtree
- Visit the Root
4. Level Order Traversal
Level Order Traversal which is also known as Breadth – First Traversal. Here Nodes are visited level by level which is started from the root and moving downwards. This method is widely used for finding the shortest path in unweighted trees and for many Graph Algorithms. It visits the nodes level by level from left to right.
- Visit the Nodes at the current level
- Move to the next level and repeat