A levelwise traversal usually performs well without much effort if you want to optimize for cache friendliness. It's not optimal iirc, but it's dead-simple and

A levelwise traversal usually performs well without much effort if you want to optimize for cache friendliness. It's not optimal iirc, but it's dead-simple and much easier on the prefetcher than an inorder traversal. Edit: Oops, TIL the eytzinger layout other comments have mentioned _is_ a levelwise traversal. Anywho, it's usually a good starting point for this kind of thing.