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 :

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.- / \ * 3 / \ 4 5

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.

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

ReplyDeleteMaxMunus 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/