Sequential hash tree traversal
You want to access every leaf in a tree, you probably do not want to start from the root every time. If you would then you need indeed $O(N \log N)$ time. If you only want to access all the leaves in the tree, do a depth-first-search traversal and you are done in $O(N)$. If you only want to have every other leaf, do the same, but ignore the "unwanted" elements.

In data structure design one often takes the leaves and put them (in order) in a double linked list. This only costs a constants factor more place, but speeds up sequential access.