Traversing a binary tree is the process of visiting each node in the tree exactly once in a systematic 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 traversals. These algorithms differ in the order in which the nodes are visited
Pre-order Traversal
To traverse a non-empty binary tree in pre-order, the following operations are performed recursively at each node. The algorithm works by:
- Visiting the root node
- Traversing the left sub-tree, and finally
- Traversing the right sub-tree.
Pre-order traversal algorithms are used to extract a prefix notation from an expression tree. For example, consider the expressions given below. When we traverse the elements of a tree using the pre-order traversal algorithm, the expression that we get is a prefix expression
In-order Traversal
To traverse a non-empty binary tree in in-order, the following operations are performed recursively at each node. The algorithm works by:
- Traversing the left sub-tree,
- Visiting the root node, and finally
- Traversing the right sub-tree
In-order traversal algorithm is usually used to display the elements of a binary search tree. Here, all the elements with a value lower than a given value are accessed before the elements with a higher value
Post-order Traversal
To traverse a non-empty binary tree in post-order, the following operations are performed recursively at each node. The algorithm works by:
- Traversing the left sub-tree,
- Traversing the right sub-tree, and finally
- Visiting the root node
Level-order Traversal
In level-order traversal, all the nodes at a level are accessed before going to the next level. This algorithm is also called as the breadth-first traversal algorithm