Breadth First Search (BFS) on a tree traverses all vertices level by level, starting from the root at level 0 (distance 0).
The maximum number of nodes at any level k in a binary tree is 2k.
To maximize the traversal index n of a vertex t located at distance 4 (level 4):
All previous levels (0,1,2,3) must contain the maximum possible number of nodes.
The vertex t must be visited as the very last node at level 4.
The maximum number of nodes from level 0 to level 4 is:
k=0∑42k=20+21+22+23+24=1+2+4+8+16=31 Thus, the maximum possible value of n is 31.