Tree Traversal

TREE TRAVERSAL
A traversal of a tree is a process to traverse a tree in a systematic way so that each vertex is visited exactly once. Three commonly used traversals are preorder, postorder and inorder. We describe here these three process that may be used to traverse a binary tree.

Preorder traversal
The preorder traversal of a binary tree is defined recursively as follows
(i) Visit the root
(ii) Traverse the left subtree in preorder.
(iii) Traverse the right subtree in preorder

Postorder traversal
The postorder traversal of a binary tree is defined recursively as follows
(i) Traverse the left subtree in postorder
(ii) Traverse the right subtree in postorder
(iii) Visit the root.

Inorder traversal
The inorder traversal of a binary tree is defined recursively as follows
(i) Traverse in inorder the left subtree
(ii) Vist the root
(iii) Traverse in inorder the right subtree
Given an order of traversal of a tree it is possible to construct a tree.

For example,
Consider the following order :
Inorder = d b e a c
We can construct the binary trees shown below in Fig. (3.36) using this order of traversal.