Link to home
Start Free TrialLog in
Avatar of dirknibleck
dirknibleck

asked on

How to calculate the depth of an elimination tournament bracket

I am looking to write code to output elimination tournament brackets. I am at a step in the process where I am trying to figure out what teams should match up with each other to start the bracket (ie if 8 teams 1 plays 8, 4 plays 5, etc) and I think I've realised that to figure this out, I need to know how deep the tournament bracket goes (in the case of 8 teams it is 4 sections deep per below) I am trying to figure out the mathematics to determining this depth. I assume it must be similar to binary tree height, but I'm not sure how to do that?

I believe that in this problem statement the tree is complete, and I know the number of nodes and leaf nodes.



Tree example

1 -
     | ---
8 -       |
           | ---
4 -       |     |
     | ---      |
5 -             |
                 | ----
2 -             |
     | ---      |
7 -       |     |
           | ---
3 -       |
     | ---
6 -

ASKER CERTIFIED SOLUTION
Avatar of yuk99
yuk99
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
actually this is called a perfect binary tree: each node has exactly 2 children and all leaves have the same depth.
the number of leaf nodes L (your number of teams) is
L =  2^H
where H is the height.

So you can find the height by doing
H = log2(L)

so... in C# you would do:
int height = (int)Math.Log(numOfTeams, 2);

of course this assumes you are indeed working with a "normal tournament". Meaning your number of team is a power of 2 = 2, 4, 8, 16, 32.