How to get a random node from a tree?

Question

It looks easy, but I found the implementation tricky. I need that for a simple genetic programming problem I'm trying to implement. The function should, given a node, return the node itself or any of its children such that the probability of choosing a node is normally distributed relative to its depth (so the function should return mostly middle nodes, but sometimes the root itself or the lowest ones - but that's not really necessary if that makes it significantly more complex, if all any node is chosen with equal probability, that's good enough).

Thanks

Answer 1

For the uniform case, if you know each node's depth, you could go left with probability size(left)/size(this), right with probability size(right)/size(this), otherwise pick the current node. A single random number at each juncture should suffice:

int r = rand() % size(this);
if (r < size(left)) { /* go left */ }
else if (r > size(left)) { /* go right */ }
else { /* pick this node */ }

In fact, with some adjustments, you can probably pass the one random number down to be used at every node. After some thought, yes you can: if you go left, use r unmodified; if you go right, subtract (size(left) - 1) from r.

For the normal distribution, just use a normally distributed random variable with a mean of half the depth to choose in advance how deep to go, then fall back to the above algorithm. Be warned that this will distribute among the middle nodes according the relative sizes of their subtrees, not uniformly.