loganwohlers

Posted on

# Bracketology and Binary Trees

Last week for a project my partner and I built a bracket simulator site in Rails that seeded fake players/teams using a gem called Faker- and then randomized their stats before seeding a bracket. This week I wanted to highlight some of that code- as well as some new tweaks I've made that allow brackets to be created recursively via a binary tree. Seeding a bracket turned out to be easy- but creating the actual appropriate matchups ended up being a bit of nightmare.

The ultimate goal in the project was to create an array of all teams- ordered by matchup in an actual bracket- remove the first two teams and have them "play" and enqueue the winner- so with that approach in mind I'm going to run through the difficulties in actually ordering a proper bracket- for reference, a properly seeded 8 team bracket in array form would look something like:

## [1,8,4,5,3,6,2,7]

This order would result in the proper matchups being played in the first round- as well as their proper placement within a bracket to ensure later rounds would play out correctly.

Lets start with the original idea that flopped almost instantly- we created an array of all teams based on their "power score" ordered from highest to lowest- to get the proper matchups all we did was iterate through the array and pull the first available team and the last available team- and while this worked for creating the proper matchups- it failed miserably in actually creating a bracket- as the 1 and 2 seeds wound up meeting in the second round- as opposed to the finals. what this resulted in:

## [1,8,2,7,3,6,4,5]

Correct matchups but in the wrong order- ie the winners of 1v8 and 2v7 would play in round 2 (as opposed to round 3/finals)

After many brackets were drawn some patterns were found:
-In the first round the two teams seeds always add up to the number of tourney entrants+1 (ie in an 8 team bracket the seeds at to 9)

-Going off of the above you can find an opposing matchup by doing
(entrants+1)-current seed

-The number of rounds played in any tournament = log2(entrants)

With the above in mind- expanding a bracket became possible

-To make a new round we would take a seed and find what it's matchup if the bracket size was doubled- so going from a 2 team to 4 team tourney- the 1 team would now play the 4 seed (calculated via #teams*2+1-seed (2*2+1-1 in this case) which comes to 4. The same math on a 2 seed results in them playing the 3 seed).

In our project we used this process to create an array of matchups- starting w/ a seeded 4 team array and expanding it however many times needed to meet the number of entrants:

``````def double_bracket(bracket)
doubled_size=bracket.length*2
doubled=[]
bracket.each do |seed|
doubled.push(seed)
doubled.push((doubled_size+1)-seed)
end
doubled
end

def bracket_order(entrants)
starting=[1,4,3,2]
if entrants==4
return starting
else
for i in 1..(Math.log2(entrants)-2)
starting=double_bracket(starting)
end
return starting
end
end
``````

Then with a correctly ordered array of seeds (bracket_order) we could map our array of ordered team objects (ordered_teams) onto it- to get a final array containing team objects in proper order- that would then be used to simulate a tournament

``````def map_bracket (ordered_teams, bracket_order)
for i in 0..(bracket_order.length-1)
team=ordered_teams[(bracket_order[i]-1)]
bracket_order[i]=team
end
bracket_order
end
``````

However we don't think about brackets like an array- we think like this (maybe turned 90 degrees)

``````                     [1, 2]---------------------2
/   \
[1,4]     [2,3]----------------4
/  \       /  \
[1,8] [4,5] [2,7] [3,6]------------8
``````

-looks awfully similar to a binary tree...

Binary Trees and Recursion

I attempted to replicate the above in Ruby with binary trees- using an array of each matchup as the node data.

To start I created a BracketNode class and a BracketTree class

``````class BracketNode
attr_accessor :data, :left, :right
def initialize (data=nil, left=nil, right=nil)
@data=data
@left=left
@right=right
end
end

class BracketTree
def initialize (overall_root=nil)
@overall_root=overall_root
end
end
``````

Then I initialized a node with the [1,2] matchup to be used as the root and expand recursively from there.

``````def build_bracket(node, entrants, curr_level)
if curr_level<=Math.log2(entrants)
node.left = BracketNode.new([node.data[0],((2**curr_level+1)-node.data[0])])
node.right = BracketNode.new([node.data[1],((2**curr_level+1)-node.data[1])])
build_bracket(node.left, entrants, curr_level+1)
build_bracket(node.right, entrants, curr_level+1)
end
nil
end
``````

It looks a little ridiculous- but it's all the same patterns from above- taking seed of each matchup and subtracting it from log2(entrants)+1 to find their opposing seed- this time recursively building bracket nodes as opposed to pushing into an array until desired # of entrants is reached.

Then there were a few helper methods- one to count the height of the tree and another to print all nodes on a current level- by combining those the below function prints all the matchups with a line between each round

``````def print_all_levels (node)
h=self.height(node)
for i in 1..h
print_level(node, i, 1)
puts "----------------------"
end
end
``````

The final code run to actually create a BracketTree and print it's matchups looks like this for a 64 team bracket

``````root=BracketNode.new([1,2])
bracket=BracketTree.new(root)
# #start on level "2" as level 1 is the [1,2] (aka the 'final')
bracket.build_bracket(root, 64, 2)
bracket.print_all_levels(root)
``````

It was fun to try and use binary trees again as they are nowhere to be found in ruby- building the bracket tree recursively ultimately served as a great challenge and reminded me once again of the power of recursion. Please leave any feedback or room for improvement in the actual code if you see any!

-Logan

DEV Community

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course.