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.
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.
3
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.
1
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.