Binary Tree Traversal (Data Structures)

What is Traversal in a Binary Tree?

In the traversal of a Binary Tree, each node is visited only once. This means "visiting each node of the tree in a specific order."

Types of Traversal

Although trees can be traversed in various ways, here we will discuss three main types of traversal:

• In-order Traversal
• Pre-order Traversal
• Post-order Traversal

1. In-order Traversal

The following steps are for In-order Traversal:

1. Traverse the Left Subtree or Left Children.
2. Visit the Root or Parent Node.
3. Traverse the Right Subtree or Right Children.

Output for the example: 9, 5, 1, 7, 2, 11, 8, 4, 3, 6

2. Pre-order Traversal

The following steps are for Pre-order Traversal:

1. First, visit the Root or Parent Node.
2. Traverse the Left Subtree or Left Children.
3. Traverse the Right Subtree or Right Children.

Output for the example: 8, 5, 9, 7, 1, 11, 2, 4, 6, 3

3. Post-order Traversal

The following steps are for Post-order Traversal:

1. Traverse the Left Subtree or Left Children.
2. Traverse the Right Subtree or Right Children.
3. Visit the Root or Parent Node.

Output for the example: 9, 1, 7, 5, 2, 3, 6, 4, 8