search a specific leaf node in a binary tree, recording the route

Question

I have a binary tree where the leaf nodes has a char( "a", "r", etc). I want to search a specific node in this tree and record the route when I found it. (It is a Huffmann's algorythm) The problem is my code just print only the last 2 subroutes( In case of the char "p", my code just cout "10" and it should print "110". The word is: paddle. The route starts from the root.

I think the problem it is the recursion. It is possible that it is double recursion, because I find in the left node and in the right node.

struct nodo{
    int frecuencia;
    nodo *izq, *der, *next;
    char letra;
    int binario; // binario it is "0" or "1" 
    int usado;

};

bool recorrerarbol(nodo *n, char letradada, string &cadena){
    if(n!=NULL){
            if(n->letra==letradada){
                    cadena=to_string(n->binario)+cadena; //n->binario it is 0 or 1
                    return true;
            }
            else{
                    if(recorrerarbol(n->izq,letradada,cadena)){
                            cadena=to_string(n->binario)+cadena;
                    }
                    else{
                            if(recorrerarbol(n->der,letradada,cadena)){
                                   cadena=to_string(n->binario)+cadena;
                    }}
            }

    }

    return false;
    }

The expected output is: for "a": 111 for "p": 110 for "d": 0 What I get: "d": 00 "p": 10 "a": 11 As you see, the problem is it only consider the last 2 levels of height . Thank you

Answer 1

I reply to myself. The problem was each if/else doesn't return True. so in some case, the function returned false when effectively it found the node needed. This is the code working: n the pointer to the root note of tree, "letradada" the letter on the node that we are looking for, cadena the string with the route(Ex: 01101)

bool recorrerarbol(nodo *n, char letradada, string &cadena){
    if(n!=NULL){
            if(n->letra==letradada){
                    cadena=to_string(n->binario)+cadena;
                    return true;
            }
            else{
                    if(recorrerarbol(n->izq,letradada,cadena)){
                            if(n->binario==-1) return true;
                            cadena=to_string(n->binario)+cadena;
                            return true;
                    }
                    else{
                            if(recorrerarbol(n->der,letradada,cadena)){
                                    if(n->binario==-1) return true;
                                    cadena=to_string(n->binario)+cadena;
                                    return true;
                    }}
            }
    }
    return false;
    }

Thank you all