I would like to estimate the number of leaves in a large tree structure for which I cannot visit each node exhaustively. Is this algorithm consistent? Does he have a name? Also, please, pedant, if I use any conditions inappropriately.
sum_trials = 0
num_trials = 0
WHILE time_is_not_up
bits = 0
ptr = tree.root
WHILE count(ptr.children) > 0
bits += log2(count(ptr.children))
ptr = ptr.children[rand()%count(ptr.children)]
sum_trials += bits
num_trials++
estimated_tree_size = 2^(sum_trials/num_trials)
source
share