Tuesday, August 2, 2011

Binary Trees Traversal Algorithm - Inorder, Preorder, Postorder

Traversals of Binary Trees

There are several well-known ways to traverse a binary tree. Let us go through  Inorder Traversal, Preorder Traversal, Postorder Traversals.

Consider that we have a tree like this -
     
DAWN
/    \
DAVE           MIKE
/   \          /    \
BETH    DAVID    GINA   PAT
\                       \
CINDI                    SUE
Inorder traversal

1) Traverse the left subtree
2) Visit the root
3) Traverse the right subtree

This consists of three overall steps: traverse the left subtree (recursively), visit the root node, and traverse the right subtree (recursively). When we "visit" a node we typically do some processing on it, such as printing out the contents of the node. For example, an inorder traversal of the above binary search tree gives us the names in this order:

BETH
CINDI
DAVE
DAVID
DAWN
GINA
MIKE
PAT
SUE

Note that we got the data back in ascending order. This will always happen when doing an inorder traversal of a Binary SEARCH Tree. In fact, a sort can be done this way. One first inserts the data into a binary search tree and then does an inorder traversal to obtain the data in ascending order. Inorder traversal of a BST always gives sorted output. Some people call this a tree sort.

Postorder traversal

1) Traverse the left subtree
2) Traverse the right subtree
3) Visit the root

As an example, let's do a postorder traversal of the binary expression tree for 4 * 5 - 3 :
         
-
/     \
*         3
/     \
4       5
First we traverse the left subtree of the whole binary tree. This is the subtree rooted at *. To do so, we apply our three steps. We traverse its left subtree, which results in printing 4. Then we traverse the right subtree, which results in printing 5. Then we visit the root, printing *. Next, we back up to where we left off with the whole binary tree. We have now traversed the left subtree, so we traverse the right subtree, printing 3. Then we visit the root, printing -. Overall we end up printing 4 5 * 3 -, the postfix form of the expression.

A postfix expression is deciphered by looking at it left to right and using the fact that each operator (such as *) applies to the two previous values. Note that the traversal always works like this: a postorder traversal of a binary expression tree yields the postfix form of the expression.


Thus, postfix notation can be achieved with POSTORDER traversal of BST.


In ordinary mathematics, in infix expressions, operators such as + and * come between the two values to which they apply. In postfix - they come after and in prefix they come before.


Preorder traversal

1) Visit the root
2) Traverse the left subtree
3) Traverse the right subtree

For practice try a preorder traversal of the same binary expression tree for 4 * 5 - 3. The result should be - * 4 5 3. This is the prefix form of the expression, that is, the form in which each binary operator precedes the two quantities to which it applies. A preorder traversal of a binary expression tree always gives the prefix form of the expression.

3 comments:

  1. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in TECHNOLOGY , kindly contact us http://www.maxmunus.com/contact
    MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.
    For Demo Contact us.
    Saurabh Srivastava
    MaxMunus
    E-mail: saurabh@maxmunus.com
    Skype id: saurabhmaxmunus
    Ph:+91 8553576305 / 080 - 41103383
    http://www.maxmunus.com/


    ReplyDelete
  2. These are the services that in our opinion do a better job at letting you fax from Gmail email. They integrate perfectly with Google’s email service and are 100% reliable for occasional and power users; what’s better, they let you try them for free before you start paying for a plan GmailFaxPro.com

    ReplyDelete