Traversing a tree means visiting all the nodes of a tree in order.

There are three different methods of traversing a binary tree:

• pre-order traversal
• in-order traversal
• post-order traversal

In each case, the algorithms for traversal are recursive - they call themselves.

Pre-order traversal

1. Start at the root node
2. Traverse the left subtree
3. Traverse the right subtree

The nodes of this tree would be visited in the order : D B A C F E G

In-order traversal

1. Traverse the left subtree
2. Visit the root node
3. Traverse the right subtree

The nodes of this tree would be visited in the order : A B C D E F G

Post-order traversal

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the root node

The nodes of this tree would be visited in the order : A C B E G F D