# Working with all leaves on a certain level of a b-tree

I want to work with a b-tree of any size. I want to do something with all leaves of the lowest depth $d$. Then if a certain condition holds, I want to recursively consider the same condition for the leaves at depth $d-1$... and so on.

What's the best performing solution with this behavoir?

• In the usual definition of b-trees, all leaves are at the same depth. – jbapple Sep 19 '11 at 13:55
• It sounds like postorder tree-traversal – Grzegorz Wierzowiecki Sep 19 '11 at 14:34
• "Then if a certain condition holds, I want to recursively consider the same condition for the leaves at depth d−1." Haven't you just answered your own question? – Jeffε Sep 25 '11 at 8:16

I assume that by "leaves" you mean "nodes," since in a B-tree all leaves are at the same depth. As soon as you've examined all nodes at the lowest depth, you've ALREADY spent $\operatorname{O}(n)$ time, so from a theoretical, asymptotic complexity standpoint you can't beat that. Pretty much whatever approach you do will get $\operatorname{O}(n)$ time, since there are at most half as many nodes at the second lowest level as at the lowest, and so at each stage if you simply traverse every node in the tree up to that depth you will still take only $\operatorname{O}(n)$ time overall.