Search code examples
algorithmgraphtreebig-ob-tree

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?

Solution

  • Traversal of a B-tree can be done in linear time - 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).