# 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. Commented Sep 19, 2011 at 13:55
• It sounds like postorder tree-traversal Commented Sep 19, 2011 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? Commented Sep 25, 2011 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.