# 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

## 3 Answers

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.

It sounds like you may be talking about the B-Tree variant B+ Tree, in which the upper levels also contain keys (or leaf information). In that case, you would to an ordinary traversal to accomplish what you want.

I think you might want to reconsider the recursive solution in this case to be an iterative one.

In that case, what you want is simply a breadth-first search on the tree, which is really an iterative algorithm. If you insist, it is possible to implement a BFS recursively: here

As for performing it in reverse order, it is impossible to know what nodes comprise the leaves of a tree without traversing it completely, (or storing auxiliary information in the nodes), so you may as well perform a BFS, store the result in a stack and then print it out from the stack (which will reverse the order).