You know the sum of the weights. Sample a random number between 0 and sum. Then, use this value to guide your search in the tree. For example, if the left branc

You know the sum of the weights. Sample a random number between 0 and sum. Then, use this value to guide your search in the tree. For example, if the left branch has weight 30 and the right branch has weight 50, the total weight is 80. If I pick 40, then I am going down the right branch. At the next child, if the left branch has weight 12 and the right branch has weight 38, the left branch spans 30-42 and the right branch spans 42-80. So you follow the left branch, because you want 40.