Clever Geek Handbook

When to use inorder, preorder and postorder traversal

I understand the code behind how to do inorder, preorder and postorder traversal in a binary search tree. However, I am confused about the application.

When will you use each? It would be very helpful to illustrate the cases where each workaround makes the most sense.

Thank!

+3


source to share


1 answer


Loop in order simply processes the items in a specific order. If, for example, you have a BST of a list of words or names, traversal in order prints them out in order.

Precedence and postorder are most commonly applied to trees other than binary search trees. For example, to evaluate an expression like this A + B * C

, you could create a tree like this:

enter image description here



To evaluate an expression, you traverse the tree in a postoperator, applying each operator to values ​​from each of its subtrees.

The traversal preview can be used for roughly the same purpose if you want (for example) to produce output in a language like Lisp, so the expression should look like (add A (mul B C))

.

+6


source






More articles:


All Articles