Count equal nodes in two binary trees

Question

I've the next problem and I can't solve it :/

There are two binary trees, arranged symmetrically One tree of the English course and another tree of the French course. Each tree has the following data: identification and student's name Each tree contains the students enrolled in those courses. A student can exist in the 2 trees enrolled. It is requested to make a function that returns the number of students who are enrolled in both courses (that is, they appear in the two trees)

How can I solve it?

I made the next code, using a search function with the two trees

typedef struct Alumno
{
    int matricula;
    char nombre[30];
}Alumno;
typedef struct NodoA* PuntA;
typedef struct NodoA 
{
    Alumno TAlumno;
    PuntA izq;
    PuntA der;
}NodoA;

int buscar(PuntA & aluI, PuntA & aluF)
{
    Alumno datoI, datoF;
    PuntA r=raizI;
    int cont = 0;
    while((r!=NULL) && (r->datoI.matricula != aluF->datoF.matricula))
    {
        if(r->datoI.matricula < aluF->datoF.matricula)
            r=r->izq;
        else
            r=r->der;
    }
    if(r!=NULL)
        cont++;

}

Sorry for the language of the code.

PS: I don't need to merge two binary trees, I need to count the equals nodes between the two trees.

Edit1: I did this code rethinking the excercise:

int buscar(PuntA raizFrances, int nro)
{
    PuntA r=raizFrances;
    while(r!=NULL && r->dato!=nro)
    {
        if(nro<r->dato)
            r=r->izq;
        else
            r=r->der;
    }
    if(r==NULL)
        return 0;
    else
        return 1;
}

void contarDobles(PuntA raizI) //MUESTRA PIMERO LA RAIZ Y DESPUES IZQUIERDA Y DESPUES DERECHA
{
    int contador = 0;
    int buscaEnF = 0;
    if(raizI!=NULL)
    {
        listarPre(raizI->izq); //1
        buscaEnF = buscar(raizI->dato, raizI->dato.matricula);
        if(buscaEnF == 1)
            contador++;
        listarPre(raizI->der);  //2
    }
    cout<<"El total de alumnos inscriptos en ambas materias es: "<<contador<<endl;
}

Possible duplicate of [How i can merge two binary trees](https://stackoverflow.com/questions/7152470/how-i-can-merge-two-binary-trees) — chang_trenton, Jun 30 '19 at 22:57
raizI undefined, datoI is not a member of NodoA, datoF is not a member of NodoA, prefer nullptr over NULL (which is not defined here anyway, although probably is defined in some headers you left out). I can answer using your variable names (easy to look up a few words) but you still have to define them for c++. My first instinct is that the language should not matter inside the code - data content vs presentation. — Kenny Ostrom, Jun 30 '19 at 23:09
First `typedef struct` is not necessary in a C++ program. All that is required is `struct`. Second, you could gather all the names in tree 1 and store them in a `std::unordered_set`. Then take each name in tree 2 and see if it exists in the set. If it does, it is a name that is in both trees. — PaulMcKenzie, Jul 01 '19 at 00:13
What you've said so far is that you have a problem statement, and you wrote code to solve the problem. The natural conclusion to make at this point is that you're done. If you're not done, you should edit your question to explain why your solution failed. What went wrong? What happened, and what did you expect would happen? Then simplify your code. We're busy and/or stupid and can only handle small chunks of code. Cut your code down to just what you need to demonstrate the point of failure of your solution. And explain that failure point -- don't assume we'll see it. — JaMiT, Jul 01 '19 at 03:05
Why not simply do a traversal of tree 1 and then for each name in tree 1, do a search of tree 2? If the name from the traversal of tree 1 is also found in the search of tree 2, you have a student enrolled in both courses. — David C. Rankin, Jul 01 '19 at 03:43

score 0 · Answer 1 · answered Jul 01 '19 at 06:48

A generic algorithm to solve this would be:

Pick an element from Tree-1 and search it in Tree-2.
Maintain a counter for all equal elements.

But there are 2 aspects to this question:

Case 1: Tree is not a Binary Search tree

Time Complexity: O(m*n)
Space Complexity: O(1)

Case 2: Tree is a Binary Search tree

Time Complexity: O(m*log(n))
Space Complexity: O(1)

A much better solution is as follows(w.r.t Time ):

Traverse the smaller tree, lets say Tree-1 and store its elements in a map M.
Traverse the larger tree and search for elements present in the map M.
Increment the counter accordingly.
Time Complexity: O(m+n)
Space Complexity: O(min(m,n))

where, m and n are sizes of Tree-1 and Tree-2 respectively.

Count equal nodes in two binary trees

1 Answers1