If you wanted to travel down a binary tree in the fairest way possible (not going down one side first then the other) you'd want to use breadth-first search, and it would look something like this:
1
2 3
4 6 5 7
8 12 10 14 9 13 11 15
But as you can see there are smaller numbers on the left and larger ones on the right. It's lopsided. to measure how unfair it is we can sum them per side.
2+4+6+8+12+10+14 = 56
3+5+7+9+13+11+15 = 63
Furthermore, we can explore smaller subtrees and see an even greater divergence by ratio the larger the tree gets:
4+8+12 = 24
5+9+13 = 27
6+10+14 = 30
7+11+15 = 33
Is there a more egalitarian way to traverse the tree? of course, here's an example of a more egalitarian traversal:
1
2 3
5 7 6 4
10 15 13 8 9 12 14 11
2+5+7+10+15+13+8 = 60
3+6+4+9+12+14+11 = 59
5+10+15 = 30
4+14+11 = 29
7+13+8 = 28
6+9+12 = 27
27 / 30 is less of a divergence then 24 / 33. But who knows if this is the best way to do it? I don't know.
So the question then becomes:
What is the most egalitarian method for traversing the tree?
Is it a static algorithm? If so does that algorithm hold true no matter the size of the tree (how many levels deep)?
Is there a limit to how fair it can be? you'll notice from the example the smallest spread I was able to manually get was 4 on the 4th level.
One might say the most overall egalitarian way to traverse the tree is to randomly choose spots on each level, but this does not guarantee subtrees to be as egalitarian as they can be.
Intuition suggests that we should be able to find a pattern that gets more and more complex the further it runs. But that doesn't change the initial design of the algorithm depending on how large the tree is.
To explain with examples:
1 levels = "L, R", 2 levels = "L, R | LL, RR, LR, RL" (the same and them more complex patterns...) [this is what I suspect]
VS
1 levels = "L, R", 2 levels = "R, L | RL, RR, LL, LR" (whole algorithm changes depending on number of levels...)
But I'd like to know the truth.