Comparing two binary search tree-CodePudding

What I'm trying to do is compare two binary search trees. This is in order to count the number of repetition that occurs on them.

First, I added this function that finds a specific element in a binary search tree.

node *search(node **tree, char val)
{
    if (!(*tree))
    {
        return NULL;
    }

    if (val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if (val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if (val == (*tree)->data)
    {
        return *tree;
    }
}

And then I was thinking about going over one of the trees and comparing with each element but it doesn't work.

int countRepetition(node *tree, node *secondTree)
{
    node *tempCount;
    tempCount = search(&secondTree, tree->data);
    if (tempCount->data < tree->data)
    {
        countRepetition(tree->left, tempCount);
    }
    else if (tempCount->data > tree->data)
    {
        countRepetition(tree->right, tempCount);
    }
    else if (tempCount->data == tree->data)
    {
        return 1;
    }
    return 0;
}

What I expect is for example: if the first tree has a, b, c, d on it and the second has a, d, m, k on it then the function should return 2. I would be so nice if someone help me, I'm dying because I'm new to C language.

This is the whole code

#include <stdlib.h>
#include <stdio.h>
typedef struct bin_tree
{
    char data;
    struct bin_tree *right, *left;
} node;
void insert(node **tree, char val)
{
    node *temp = NULL;
    if (!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if (val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    } 
    else if (val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }
}
node *search(node **tree, char val)
{
    if (!(*tree))
    {
        return NULL;
    }

    if (val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if (val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if (val == (*tree)->data)
    {
        return *tree;
    }
}

int countRepetition(node *tree, node *secondTree)
{
    node *tempCount;
    tempCount = search(&secondTree, tree->data);
    if (tempCount->data < tree->data)
    {
        countRepetition(tree->left, tempCount);
    }
    else if (tempCount->data > tree->data)
    {
        countRepetition(tree->right, tempCount);
    }
    else if (tempCount->data == tree->data)
    {
        return 1;
    }
    return 0;
}

char main(char argc, char const *argv[])
{
    node *root, *secondRoot;
    node *tmp;

    root = NULL;
    /*Here i create the first tree*/
    insert(&root, 'a');
    insert(&root, 'b');
    insert(&root, 'c');
    insert(&root, 'd');
    insert(&root, 'j');
    insert(&root, 'k');
    insert(&root, 'z');
    //Here i create the second tree
    insert(&secondRoot, 'p');
    insert(&secondRoot, 'b');
    insert(&secondRoot, 'f');
    insert(&secondRoot, 'd');
    insert(&secondRoot, 'g');
    insert(&secondRoot, 'k');
    insert(&secondRoot, 'h');

    printf("\n%d\n", countRepetition(root, secondRoot));

    return 0;
}

CodePudding user response：

Some major errors here

first your code does not initialize root and secondRoot here

 node *root, *secondRoot;

should be

    node* root = NULL, * secondRoot = NULL;

next this line

 tempCount = search(&secondTree, tree->data);

does not check to see if NULL was returned , so the next line

 if (tempCount->data < tree->data)

fails in that case.

Note the double pointer passing is not needed and makes you code very hard to read. You only need it on insert where you actually allocate the root node. All other calls do not change the passed in tree pointer. I would have a 'createTree' function that returns an empty tree, and then insert does not need that special case code

but mainly - learn to use your debugger.

CodePudding user response：

Some of the issues:

The declaration of main is wrong. It should be:
```
int main(int argc, char const *argv[])
```
secondRoot is not initialised. It should be initialised to NULL
search does not return a value after having made a recursive call. It should return that recursive call's result.
search should not need a pointer-pointer argument. Since it does not alter the tree, let be its root, it only needs a single-pointer argument.
countRepetition should check whether tempCount is NULL, to avoid undefined behaviour with tempCount->data.
Given that search either returns a node with the searched value or NULL, the tests tempCount->data > tree->data and tempCount->data < tree->data don't make sense. These should never be true.
The only return statements in countRepetition return 0 or 1, so there is no way this function would return another integer value.
It looks like you wanted to implement some binary search, but this means that even if the above points would be corrected, you would never visit all nodes in the first tree, so you would very likely miss some matching values.

Time Complexity

It seems your idea was to visit every value in the first tree, and for each perform a search in the second tree, and then count the matches. If we call