# Time complexity of inorder run on B+ tree (without leavesa link)

I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each node you pass maximum $4$ time. The upper limit is $O(n)$. So in B+ tree it's limit by $2*B$ times. Is it right?

• In a B+ tree, to do an in-order traversal, one need only traverse the leaves as they link to each other. And by design, at least a certain fraction of each leaf is full. So it is $O(n)$. – Reinstate Monica Mar 8 '18 at 1:05
• Thank you @Solomonoff'sSecret . I didn't mention it but I mean the implementation without links between the leaves. – ChaosPredictor Mar 8 '18 at 10:30
• Note that the number of nodes in a B+ tree is $\theta(n)$ because the number of nodes is twice the number of leaves less one, and the number of edges is one less than the number of nodes, which is also $\theta(n)$. So traversal is still $\theta(n) \subset O(n)$. – Reinstate Monica Mar 8 '18 at 14:21