Palabra en un árbol V40142

Diremos que un BinTree<char> T representa una palabra word, formada por los caracteres $c_1c_2\ldots c_n$, con $n\geq 0$, si hay un camino en el árbol comenzando desde la raíz y de longitud $n$ tal que los valores de los nodos del camino forman word. Implementad eficientemente la función count_word_in_paths, especificada a continuación:

/**
 * @pre  `word` tiene al menos una letra
 * @post se retorna el número de caminos en T que representan
 *       la palabra word desde la raíz
 */
int count_word_in_paths(const vector<char>& word, const BinTree<char>& T);

Por ejemplo, para la palabra "dia" si el árbol es t1, el resultado es 0, si el árbol es t2 el resultado es 3 y si el árbol es t3 el resultado es 1.

t1 = d         t2 = d         t3 = d
    / \            / \            / \
   d   d          i   i          i   i
  / \            /   / \            / \
 w   i          a   a   a          a   b
    / \        / 
   k   a      r 

Observación

Solo es necesario que enviéis el código de la función en un archivo .cc, en el icono del gatito tenéis un .tar para poder compilar y probar vuestra solución.