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