facebook like button

12 October, 2011

Inorder, Preorder and Post-Order traversal : An overview

The Idea:
Lets first have a look at some mathematical side. The Infix, Prefix and Post-fix notations are exactly analogous to the In-order, Preorder and Post-order traversal of trees.
Have a look at the expresstion:
a + b
     This is a familiar expression to all of us. Here + is an operator with a and b as operands. This is one way to write sum of a and b. This way is called in-fix notation. In this way we write operator in between the operands. This is the only used method for writing expressions for human understanding. Thats why everybody is familiar to this method. But this is not the only way to be used for every purpose. there are 2 more ways.
     Prefix notation: In this way of writing expressions the operator comes first which is followed by the operators. The same expression can be written in Prefix notation as:
+ a b
     Postfix notation: In this way of writing expressions the operator comes last after both the operands have been written. The same expression can be written in Prefix notation as: 
a b +

Analogy comes from here. Have a look at the above image.
Its a tree with + at parent node and 2 and 3 as child nodes. Now we have
Infix: 2 + 3
Prefix: + 2 3
postfix: 2 3 +
    We see that it is the position of operator which changes and decides which fix notation is this. The relative positions of operands are always same.
    This is about expressions writing. Now lets move to traversal of trees in data-structures topic. In the same manner as in the case of expressions in trees also left child will always be accessed before the right. It is the root which decides which type of traversal it is.
     InOrder Traversal: In this way of traversing tree the root is accessed first after that the children are accessed.
     PreOrder Traversal: In this way of traversing tree one child is accessed first and then the root is accessed after that the other child is accessed.
     PostOrder Traversal: In this way of traversing tree the root is accessed after both of the children are accessed.
   here this concept is explained with the basic tree consisting of only 3 nodes but this holds true for any tree(binary tree). Recursion will play very important role in tree traversal. We can store a mathematical expression in tree and then that can be printed in any order using inorder, preorder and postorder traversal giving infix, prefix and post-fix form of that expression respectively. Obviously this is not the only use of trees.

No comments:

Post a Comment

feel free to ask your doubts... if any
you can post your doubts on
www.facebook.com/programsimply