• Traversing a binary tree is a process of visiting each node in the tree exactly once in a symmetric way.

• Unlike linear data structures in which the elements are traversed sequentially, tree is a non linear data structure in which the elements can be traversed in many different ways.

There are different algorithms for tree traversal:

A. Pre-order algorithm:

• To traverse a non empty binary tree in pre order, the following operations are performed recursively at each node.

• The algorithm starts with the root node of the tree and continues by,

1. visiting the root node.

2. Traversing the left sub tree.

3. Traversing the right sub tree.

• The ps order traversal of the tree is given as A, B, C. root node first, the left sub tree next and then the right sub tree.

• In this algorithm, the left sub tree is always traversed before the right sub tree.

Example.

Preorder traversal order: A, B D, G, H ,C , E , C , F , I , J ,K .

B. In order algorithm:

• To traverse a non empty binary tree in in order, the following operations are performed recursively at each node.

• The algorithm starts with the next node of the tree and continues by :

1. Traversing the left sub tree.

2. Visiting the root node.

3. Traversing the right sub tree.

• The in - order traversal of the tree is given as B, A and C.

• In this algorithm, left sub tree first, the root node next and then the right sub tree will be traversed.

In-order traversal order:

G,D,H,L,B,E,A,C,I,F,K,J.

C. Post order algorithm:

• To traverse a non empty binary tree in post order, the following operations are performed recursively at each node.

• The algorithm starts with the root node of the tree and continues by,

1. Traversing the left sub tree.

2. Traversing the right sub tree.

3. Visiting the root node.

• The post order traversal of the tree is B, C and A.

• In this algorithm, the left sub tree is always traversed before the right sub tree, and the root node.

Post-order traversal order:

G,L,H,D,E,B,I,K,J,F,C,A.