+1 I don't see why not. Pre-order and post-order are also pretty textbook traversals. I don't imagine they'll be used very heavily, but they're certainly good for learning purposes.
Perhaps instead of newtypes for each of these, we can just provide the corresponding "traverse" function. These types unsurprisingly correspond to lens's Traversal (Tree a) (Tree b) a b.
depthFirst :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
depthFirst = ...
preOrder :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
preOrder = ...
postOrder :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
postOrder = ...
inOrder :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
inOrder = traverse