I have a generic binary tree which is used for calculating combinations of things - i.e. a powerset in set parlance.Most of the time it is used for calculating subsets of size N.As a real world example, say we have 10 players in a basketball squad and we want to calculate every starting 5.In my particular problem domain, this is run millions of times so I'm trying to squeeze every bit of performance out of it that I can. Where I am only interested in subsets, I'm trying to prune the tree as I build it since it seems to be here where the bottleneck lies. The tree is built from the leaves down so I guess I could count ancestors as I build and (in the example above) stop that branch whenever I have 5, but while this would work, I think it would probably add more overhead than it would save. Any thoughts (aside from trying it)?EXAMPLEThis data:Yields this profile:AddGeneration builds each level of the tree while TraverseTree pulls the results. As you can see there is something like a 99:1 split in terms of effort between the two.
Binary tree pruning
c#;performance;language agnostic;binary tree