Paraula en un arbre V40142

Direm que un BinTree<char> T representa una paraula word, formada pels caràcters $c_1c_2\ldots c_n$, amb $n\geq 0$, si hi ha un camí a l’arbre començant des de l’arrel i de longitud $n$ tal que els valors dels nodes del camí formen word. Implementeu eficientment la funció count_word_in_paths, especificada a continuació:

/**
 * @pre  `word` té almenys una lletra
 * @post es retorna el nombre de camins que representen
 *       la paraula word des de l'arrel
 */
int count_word_in_paths(const vector<char>& word, const BinTree<char>& T);

Per exemple, per a la paraula "dia" si l’arbre és t1, el resultat és 0, si l’arbre és t2 el resultat és 3 i si l’arbre és t3 el resultat és 1.

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

Observació

Només cal que envieu el codi de la funció en un fitxer .cc, a la icona del gatet teniu un .tar per poder compilar i provar la vostra solució.