Practice: Counting the Matches in a Knockout Bracket

Each match is a node whose two children are the matches that fed it.

A knockout bracket is a tournament in which every match has two players, the loser goes out, and the winner moves on to the next match, until one player is left. This card covers a bracket as an exercise in reading a binary tree and writing recursive functions that combine two results, with an answer to check yours against.

Six players enter. Ana plays Ben in the first quarter-final, and the winner plays Cai in the first semi-final. Dev plays Eli in the second quarter-final, and the winner plays Fay in the second semi-final. The two semi-final winners meet in the final.

Draw the bracket as a binary tree with the final at the root. Say what the leaves are and what every other node is.
Write matches(node), which returns how many matches are played in the part of the bracket below and including node, and rounds(node), the most matches any one player must win to come out of that part on top. Name each function's base case, the input it answers without calling itself, and its combine step.
Give both answers for this bracket, then predict them for 8, 64 and 100 players, with each bracket split as evenly as possible.

An answer: the bracket as a tree, the two functions, and the counts

The leaves are the players and every other node is a match, whose two children are what feed it: a player, or the match whose winner arrives. A leaf has no match below it, so both functions return 0 there, which is the base case. matches combines by adding: 1 for the node's own match, plus the matches below each side. rounds is the bracket's height in edges, so it combines as height does: 1 more than the larger side. Each note gives what the two calls returned at that node.

The six-player bracket, with the matches and rounds each node returned

final, 5 matches, 3 rounds
- semi-final 1, 2 matches, 2 rounds
  - quarter-final 1, 1 match, 1 round
    - Ana
    - Ben
  - Cai
- semi-final 2, 2 matches, 2 rounds
  - quarter-final 2, 1 match, 1 round
    - Dev
    - Eli
  - Fay

The listing builds this bracket, and evenly split ones for the predictions:

knockout_bracket.pypy

class Node:
    def __init__(self, name, left=None, right=None):
        self.name = name
        self.left = left
        self.right = right


def matches(node):
    if node.left is None and node.right is None:
        return 0
    return 1 + matches(node.left) + matches(node.right)


def rounds(node):
    if node.left is None and node.right is None:
        return 0
    return 1 + max(rounds(node.left), rounds(node.right))


def counted(count, singular, plural):
    return f"{count} {singular if count == 1 else plural}"


def describe(node):
    return f"{counted(matches(node), 'match', 'matches')}, {counted(rounds(node), 'round', 'rounds')}"


def full_bracket(players):
    if players == 1:
        return Node("player")
    half = players // 2
    return Node("match", full_bracket(half), full_bracket(players - half))


final = Node(
    "final",
    Node("semi-final 1", Node("quarter-final 1", Node("Ana"), Node("Ben")), Node("Cai")),
    Node("semi-final 2", Node("quarter-final 2", Node("Dev"), Node("Eli")), Node("Fay")),
)
print(f"six players: {describe(final)}")
for side in (final.left, final.right, final.left.left, final.left.right):
    print(f"  {side.name}: {describe(side)}")
for players in (8, 64, 100):
    print(f"{players} players: {describe(full_bracket(players))}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

six players: 5 matches, 3 rounds
  semi-final 1: 2 matches, 2 rounds
  semi-final 2: 2 matches, 2 rounds
  quarter-final 1: 1 match, 1 round
  Cai: 0 matches, 0 rounds
8 players: 7 matches, 3 rounds
64 players: 63 matches, 6 rounds
100 players: 99 matches, 7 rounds

Six players need 5 matches, and the champion wins 3. The match count is always one less than the number of players, 7, 63 and 99, because every match sends exactly one player home and all but one must go. The tree says the same: a tree in which every node has two children or none has one fewer inner node than leaves. Rounds grow far more slowly, 3, 6 and 7, because each round halves the field, so an even bracket of n players has a height of log n rounded up, with the logarithm base 2.

← → move through sections and cards