<p>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.</p>

CC BY-SA 3.0
2011-09-19T22:26:03.020Z
2011-09-19T22:26:03.020Z
Michael Cohen
<p>I think you might want to reconsider the recursive solution in this case to be an iterative one.</p>

<p>In that case, what you want is simply a <a href="http://en.wikipedia.org/wiki/Breadth-first_search" rel="nofollow noreferrer">breadth-first search</a> on the tree, which is really an iterative algorithm. If you insist, it is possible to implement a BFS recursively: <a href="https://stackoverflow.com/questions/2969033/recursive-breadth-first-travel-function-in-java-or-c">here</a></p>

<p>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).</p>

CC BY-SA 3.0
2011-09-20T09:04:39.433Z
2011-09-20T09:04:39.433Z
2017-05-23T11:33:33.907Z
ankit
<p>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.</p>

CC BY-SA 3.0
2011-09-20T05:01:41.417Z
2011-09-20T05:01:41.417Z
xpda
<p>I want to work with a <a href="http://en.wikipedia.org/wiki/B-tree" rel="nofollow">b-tree</a> of any size. I want to do something with <strong>all</strong> 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.</p>

<p>What's the best performing solution with this behavoir?</p>

CC BY-SA 3.0
2011-09-19T13:55:08.853Z
In the usual definition of b-trees, all leaves are at the same depth.
jbapple
CC BY-SA 3.0
2011-09-19T14:34:21.807Z
It sounds like [postorder tree-traversal](http://en.wikipedia.org/wiki/Tree_traversal)
Grzegorz Wierzowiecki
CC BY-SA 3.0
2011-09-25T08:16:30.523Z
"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ε
<ds.data-structures><tree>
Working with all leaves on a certain level of a b-tree
derphil
# Working with all leaves on a certain level of a b-tree

(Asked by: username_0 on 2011-09-19)

I want to work with a [b-tree](http://en.wikipedia.org/wiki/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?

**Tags:** ds.data-structures, tree
> **Comments:**
> **username_1**: In the usual definition of b-trees, all leaves are at the same depth.  
> **username_2**: It sounds like [postorder tree-traversal](http://en.wikipedia.org/wiki/Tree_traversal)  
> **username_3**: "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?  

---

## 3 answers

### Answer by username_4 on 2011-09-19. Score: 1 | Accepted answer

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.


---

### Answer by username_5 on 2011-09-20. Score: 0

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](http://en.wikipedia.org/wiki/Breadth-first_search) on the tree, which is really an iterative algorithm. If you insist, it is possible to implement a BFS recursively: [here](https://stackoverflow.com/questions/2969033/recursive-breadth-first-travel-function-in-java-or-c)

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).


---

### Answer by username_6 on 2011-09-20. Score: 0

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.


---

