Traversal Algorithms

Tree Traversal

Tree Traversal is the process of visiting (checking or updating) each node in a tree data structure, exactly once. Unlike linked lists or one-dimensional arrays that are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in depth-first or breadth-first order.

There are three common ways to traverse a tree in depth-first order:

1. In-order
2. Pre-order
3. Post-order

Let’s begin with the Pre-order Traversal.

Pre-order Traversal

Here is the algorithm for a pre-order traversal:

1. Check if the current node is empty/null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order method.
4. Traverse the right subtree by recursively calling the pre-order method.