Árbol general de carácteres en Java

De nuevo aquí xd. Estoy haciendo una práctica en la facultad y necesitaría algo de luz implementando un TAD.
El TAD en concreto es un árbol general que debe almacenar consultas que previamente se han insertado en un buscador. De este modo, cuando otra persona insertar en el buscador una cadena, que es un prefijo Ej. coche de se .., debería de sugerir, por ejemplo, coche de segunda mano.
La cuestión de todo esto es que el árbol es de carácteres y no de consultas enteras, tiene lógica de que esto sea así, pues el recorrido y búsqueda en el árbol será muchísimo mas rápido.

El árbol es una estructura de datos definida de forma recursiva y como tal, todas las operaciones que tiene pueden realizarse con este tipo de algoritmos. Pero tenemos un problema. El problema reside en que 1) tanto la interfaz como la implementación del TAD, no puede ser modificada. Por otra parte, el árbol es utilizado a través de otra clase, llamada depósito de consultas. Por lo que la recursión de forma interna en el TAD no es válida. Hay que tener en cuenta que un árbol te permite añadir una raíz y unos hijos.

Tengo una primera aproximación que no funciona del todo y además, el tutor me ha dicho...me ha dicho que es una puta mierda sutilmente jajajajaj. Que mire ejemplos que hay miles. Yo no los encuentro.He de admitir que a mi, el código tampoco me convence nada de nada.

@Override
    public void incFreqQuery(String query) {
        char[] word              = query.toCharArray();
        TreeDynamic<Node> branch = queryList;
        

    ListIF< TreeIF<Node> > subBranchs;
    for ( int i = 0; i < word.length; i++ ) {
        
        subBranchs  = branch.getChildren();

        boolean      found   = false;
        
        TreeIF<Node> node    = null;
        while ( !found && !subBranchs.isEmpty() ) {
           node = (TreeIF<Node>) subBranchs.getFirst();
           if ( node.getRoot().getElement().toString().equalsIgnoreCase( "" + word [i] ) ) {
               branch = (TreeDynamic<Node>) node;
               found  = true;
           } else
                subBranchs = (ListIF<TreeIF<Node>>) subBranchs.getTail();
        }
                    
        if ( ! found ) {
           TreeDynamic<Node> newNode = new TreeDynamic<>();
                             newNode.setRoot ( new Node( word[i]) );
           branch.addChild (newNode);
           
           if ( i == ( word.length - 1 ) )
               newNode.addChild( new TreeDynamic<Node> ( new Node(1) ));
           
           branch = newNode;
        } else
        {
            if ( i == ( word.length - 1 ) )
            {
                int c = (int) branch.getChildren().getFirst().getRoot().getElement();
                branch.getChildren().getFirst().getRoot().setElement( ++c );
            }
        }
    }
}

No pido soluciones. Solo algo de ayuda para ver si consigo ver la luz!
Gracias de antemano.