a tree

[hamsterman]

I have a tree that looks like this:

struct NODE{
    vector<NODE*> children;
};

I want to randomly choose one node with equal probability to choose the root or a leaf. Do you know a quick way to do this?

I was thinking I could either generate a vector of NODE** that contains all nodes and then choose one, or iterate through the tree and approximate the probability to choose a node according to its size. Neither seems very efficient though.

[Galik]

You could keep a note of the total number of nodes. Generate a number between 0 and that number. Then count your way that many nodes through the tree.

[hamsterman]

thanks. didn't think about that..