Question 21

In a binary tree, let the root be at distance 0 (level 0). A vertex $t$ at distance 4 is at level 4.

Breadth First Search (BFS) explores all vertices level by level:

• All vertices at level 0 are visited first,
• then all vertices at level 1,
• then all vertices at level 2,
• then all vertices at level 3,
• and finally vertices at level 4.

To maximize the index $n$ at which vertex $t$ is visited, the binary tree must contain the maximum possible number of vertices at each level up to level 4, and $t$ must be the last vertex visited at level 4:

• Level 0: at most $2^0 = 1$ vertex
• Level 1: at most $2^1 = 2$ vertices
• Level 2: at most $2^2 = 4$ vertices
• Level 3: at most $2^3 = 8$ vertices
• Level 4: at most $2^4 = 16$ vertices

The maximum total number of vertices up to and including the last vertex of level 4 is:

Thus, the maximum possible value of $n$ is 31.