PUERTA | GATE-CS-2016 (Conjunto 2) | Pregunta 21

Breadth First Search (BFS) se inicia en un árbol binario a partir del vértice raíz. Hay un vértice t a una distancia de cuatro de la raíz. Si t es el n-ésimo vértice en este recorrido BFS, entonces el valor máximo posible de n es ________

[Esta pregunta era originalmente una pregunta para completar los espacios en blanco]

(A) 15
(B) 16
(C) 31
(D) 32

Respuesta: (C)
Explicación: Sería el Node número 31 para la distancia dada 4.

Por ejemplo, si consideramos la distancia 2, el Node G resaltado a continuación puede ser el Node más lejano en la posición 7.

            A
         /    \
        B       C
       / \     / \
      D   E   F   G

Solución alternativa:
t es el n-ésimo vértice en este recorrido BFS a la distancia cuatro de la raíz. Así que la altura del árbol es 4.
Número máximo de Nodes = 2^{h+1} − 1 = 2^{5} − 1 = 31
A la distancia cuatro, el último Node es 31. opción (C).

Cuestionario de esta pregunta