Does the system allow you to write to that database?
Store the partial total of the number of leaves at each collection node (like storing the number of files at each directory node) as you traverse back up the collection tree.
When modify the collection tree, invalidate the node partial totals in that path as part of the process.
That way, you only have to recursively update the parts of the collection tree that happen to be invalid when you need the leaf and branch count(s).
Otherwise, the expansive traverse and count has already been done, just collect sub-totals as deep as required at the moment.
"Hack is just a four letter word." - - With apologies to B. Dylan