Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This may be very naive, but I was wondering, it the context of binary trees (plain, sorted and balanced), of all the traversal types:

  • depth-first pre-order
  • depth-first in-order
  • depth-first post-order
  • breadth-first

what's the actual utility of pre and post-order ones? I mean, is there some type and/or configuration of binary tree in which pre and/or post-order traversal would give an(some) advantage(s) over the other two?

AFAICS, there are certain types and configuration of binary trees for which in-order and breadth-first might give a certain advantage:

  • for a balanced binary tree any depth-first traversal will use less memory storage space as compared to breadth first (eg. for balanced binary tree of 6 or 7 nodes, height is 2 so any depth-first traversal will need to store a max of 2 nodes at any given time, while last level has 3 or 4 nodes so breadth-first traversal would need to store up to 3 or 4 nodes at some point). In this case using in-order traversal uses the least amount of memory and visits the nodes in their natural order.

  • for a non-balanced binary tree, if it's close to the worst-case insertion scenario, traversing it breadth-first would use less memory as compared to any of the depth-first traversals. So in this case breadth-first offers an advantage. In-order traversal has the again the advantage of visiting values in their natural order.

However I can't think of a situation where pre and post-traversal would give an advantage over the other two.

share|improve this question
add comment

4 Answers

The point of having different algorithms to deal with binary trees is not to do things with trees. On this abstract level, one order is largely as good as any other, since you only get abstract symbols out of the procedure.

But trees are typically used to represent interesting stuff, and that can make a big difference in the outcome. For instance, if the nodes represent search states in a complete search through a big domain (maybe even an infinite domain), descending first vs. processing first not only determines in which order the results are found, it can even determine whether you will ever find any solutions at all. The point is easiest to see with infinite domains: if you descend incautiously, you might overlook a solution that lies quite high up in the tree, simply because you took a wrong turn. But in practice, since memory and disks are finite as well, this even applies to domains that are simply very large rather than truly infinite.

share|improve this answer
add comment

You need to do various things with trees, like translate between the data structure and some serial representation, like on a file or in a language.

So, for example, suppose you have a parse tree like this:

    *
   / \
  +   \
 / \   \
A   B   C

You could serialize it as * + A B C by walking it in prefix order, or as A B + C * by walking it in postfix order. If you work at all with language processors, such things need to be second-nature.

share|improve this answer
    
Very good example! And note how in-order-traversal would yield A + B * C, which is much easier to understand for normal users than either prefix of postfix order. –  Kilian Foth Feb 11 '13 at 15:10
3  
@KilianFoth except that is not what the tree says - it says (A + B) * C, at least to my eyes. Although my HP-28s fingers like the A B + C * version just fine. :-) –  sdg Feb 11 '13 at 17:32
    
@Kilian: sdg is right. With inorder, you have to be concerned with precedence, unless you put parentheses around everything. –  Mike Dunlavey Feb 11 '13 at 19:42
add comment

The wikipedia article has a nice concise description of when you would want to use the different types of depth-first search:

  • Pre-order traversal while duplicating nodes and values can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.
  • In-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
  • Post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree.

It boils down to the logistical needs of an algorithm. For example, if you don't use post-order traversal during deletion, then you lose the references you need for deleting the child trees.

share|improve this answer
add comment

While all the answers were helpful, it is really this article which comes closest to the answer I wanted (and is also closer to my level of understanding).

share|improve this answer
    
You could have provided this answer as a comment or an edit to your original question. As it is, you stand liable to be accused of rep-whoring by accepting your own answer. –  pmcs Oct 9 '13 at 3:04
    
@pmcs: I see your point. I'll un-make my (this) answer as the accepted answer. Honestly though: it's not rep whoring, I really think that the article linked in my post above represents the best answer to the question –  Shivan Dragon Oct 9 '13 at 11:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.