GATE CS 2016 Set 2 Q11 — Graph Traversals (BFS, DFS)

To find the maximum possible value of $n$ (the position of vertex $t$ in the BFS traversal), we need to maximize the number of vertices visited before $t$.

In a BFS traversal of a tree starting from the root, vertices are visited level by level. Let the root be at Level 0.

• A vertex $t$ at a distance of $4$ from the root lies at Level 4.
• All vertices at Levels 0, 1, 2, and 3 must be visited before any vertex at Level 4 is visited.

To maximize the index $n$ of $t$, we must maximize:

1. The number of vertices in Levels 0 to 3.
2. The number of vertices in Level 4 that are visited before $t$.

Since the graph is a binary tree, the maximum number of vertices at any level $i$ is $2^i$:

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

The maximum number of vertices in Levels 0 through 3 is: $$1 + 2 + 4 + 8 = 15$$

At Level 4, there can be a maximum of $2^4 = 16$ vertices. To make $t$ the last vertex visited at Level 4, we assume Level 4 is fully populated and $t$ is the rightmost (last) vertex visited at this level.

Thus, the position $n$ of $t$ in the BFS traversal is: $$n = \text{(Vertices in Levels 0 to 3)} + \text{(Vertices in Level 4 up to and including } t\text{)}$$ $$n = 15 + 16 = 31$$

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