'What is the big O of counting elements in a B tree

For example if I have a tree which nodes have a structure:

{ type: 'document' } or {type: 'note'}

If I wanted a count of all nodes that have type note what would be count big O for a B tree?

algorithmgraphtreebig-ob-tree


Solution 1:[1]

Traversal of a B-tree can be done in linear complexity - i.e. O(n). This is because each of the n nodes should be visted once.

You will spend a constant time in each node (checking the type of the node and incrementing a counter, doesn't depend on the size of the tree) - that's O(1).

Therefore the overall complexity should be still linear - O(n).

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 wohlstad

Related Questions