**1 Answer**

written 8.2 years ago by | • modified 8.2 years ago |

To traverse a binary tree means to visit each node of the tree exactly once in a systematic fashion. Binary tree is non-linear data structure. Hence, we can’t traverse it like a linked list is a sequential manner but it requires a different approach. We mainly have three algorithms for traversing binary tree. The difference in them is when they visit which nodes.

1.**Pre-order traversal**

To traverse a non-empty binary tree by pre-order method, the following operations are performed recursively until all nodes are visited:

i. Visit the root node.

ii. Traverse the left sub-tree fully.

iii. Traverse the right sub-tree.

- Consider the example beside. The pre-order traversal of the tree is A,Q,W,Z,C,H,G,D
- As we see, we traverse the root node first, then the left sub-tree, then move to right sub-tree.
- The keyword ‘pre’ here means that the root node is accessed the very first.
- It is also known as depth first traversal.
- The pre-order traversal is used to extract a prefix notation from an expression tree.

2.**In-order traversal**

To traverse a non-empty binary tree by in-order method, the following operations are performed recursively until all nodes are visited:

i. Traverse the left sub-tree.

ii. Now, visit the root node.

iii. Then, finally traverse the right sub-tree.

- Consider the example above. The in-order traversal of the tree is Q, Z, W, C, A, H, D, G
- As we see, we traverse the left sub-tree first, then we moved to the root node and finally the right sub tree.
- The keyword ‘in’ specifies that the root node is accessed between left and right node.
- In-order traversal is used to display the elements of a binary search tree.

3.**Post-Order traversal.**

To traverse a non-empty binary tree by post-order method, the following operations are performed recursively until all nodes are visited:

i. Traverse the left sub-tree.

ii. Now, move to the right sub tree

iii. Then, finally visit the root node.

Consider the example above. The post-order traversal of the tree is Z, C, W, Q, D, G, H, A

- As we see, we traverse the left sub-tree first, then the right sub-tree and finally we visit the root node.
- The keyword ‘post specifies that the root node is accessed after we visit the left and right sub-trees.
- They are used to extract post fix notation from an expression tree