Breadth First Search (BFS) is started on a binary tree beginning from the root…
2016
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex \(t\) at a distance four from the root. If t is the \(n\)-th vertex in this BFS traversal, then the maximum possible value of \(n\) is _____________ .
Attempted by 94 students.
Show answer & explanation
Correct answer: 31
Answer: 31
Key idea: In a binary tree the maximum number of nodes at distance d from the root is 2^d. Breadth-first search visits nodes level by level, so to maximize the position of a vertex at distance 4 make it the last node visited on level 4.
Number of nodes on level 0 through 4:
Level 0: 1 node
Level 1: 2 nodes
Level 2: 4 nodes
Level 3: 8 nodes
Level 4: 16 nodes
Summing these gives 1 + 2 + 4 + 8 + 16 = 31. If the vertex at distance 4 is placed as the last node on that level, it will be the 31st vertex visited by BFS, which is the maximum possible n.
A video solution is available for this question — log in and enroll to watch it.