Problema número 290

Altura de un árbol binario

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB

La altura de un árbol binario se define recursivamente de la siguiente manera:

  • si el árbol es vacío su altura es 0; y
  • si el árbol no es vacío su altura es 1 más que el máximo de las alturas de sus hijos.

De los siguientes árboles, el de la izquierda tiene altura 3 y el de la derecha tiene altura 4.

Tres árboles binarios, los dos primeros equilibrados

Dado un árbol binario, ¿sabrías calcular su altura?

Entrada

La entrada comienza indicando el número de casos de prueba que vendrán a continuación. Cada caso consiste en una cadena de caracteres con la descripción de un árbol binario: el árbol vacío se representa con un punto (.); un árbol no vacío se representa con un * (que denota la raíz), seguido primero de la descripción del hijo izquierdo y después de la descripción del hijo derecho. Los árboles nunca contendrán más de 5.000 nodos.

Salida

Para cada árbol, se escribirá una línea con su altura.

Entrada de ejemplo

2
***..*..*..
**..**..**..*..

Salida de ejemplo

3
4