[SOLVED] Comparing two binary search tree

Issue

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;
}

Solution

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 𝑚 the number of nodes in the first tree, and 𝑛 the number of nodes in the second tree, then this represents a time complexity of O(𝑚log𝑛).

For small trees, this is fine, but if 𝑚 and 𝑛 are both large, we can do better. We could iterate the values in the first tree in sorted order (i.e. in inorder traversal), and do this for the second tree as well, at the same time. We would go to the next node in one of the two traversals when it is the lesser of the two currently visited nodes. This way we walk through both trees in "tandem". As the visit is in order of value, we will be sure to find equal values this way.

This alternative algorithm represents a time complexity of O(𝑚+𝑛). When 𝑚 and 𝑛 have the same order of magnitude, this is a better time complexity than the first algorithm offers.

Implementation

I would suggest creating a kind of iterator for visiting nodes in inorder sequence, so that you can at any time ask for the successor of a node in that traversal. For this you'd need a stack (e.g. linked list), so to know which are the ancestors of the current node that still need to be visited.

Here is the code that would need to be added for that aspect:

// Stack implementation
typedef struct node_list
{
    struct bin_tree *node;
    struct node_list *next;
} nodeList;

void pushFront(nodeList **head, node *newNode) {
    nodeList *newHead = malloc(sizeof(nodeList));
    newHead->node = newNode;
    newHead->next = *head;
    *head = newHead;
}

node *popFront(nodeList **head) {
    nodeList *front = *head;
    node *frontNode = front->node;
    *head = front->next;
    free(front);
    return frontNode;
}

// Inorder tree iterator implementation
nodeList *treeIterator(node *root) {
    if (root == NULL) return NULL;
    nodeList *head = NULL;
    pushFront(&head, root);
    // Push path to left-most node (which has least value)
    while (root->left != NULL) {
        root = root->left;
        pushFront(&head, root);
    }
    return head;
}

node *next(nodeList **head) {
    if (*head == NULL) return NULL;
    node *currentNode = popFront(head);
    node *nextNode = currentNode;
    if (nextNode->right != NULL) {
        nextNode = nextNode->right;
        pushFront(head, nextNode);
        while (nextNode->left != NULL) {
            nextNode = nextNode->left;
            pushFront(head, nextNode);
        }
    }
    return currentNode;
}

The actual algorithm can then be implemented as follows:

int countRepetition(node *tree, node *secondTree)
{
    int count = 0;
    
    nodeList *iterator1 = treeIterator(tree);
    nodeList *iterator2 = treeIterator(secondTree);

    node *node1 = next(&iterator1);
    node *node2 = next(&iterator2);
    while (node1 != NULL && node2 != NULL) {
        if (node1->data < node2->data) {
            node1 = next(&iterator1);
        } else if (node1->data > node2->data) {
            node2 = next(&iterator2);
        } else {
            count++;
            node1 = next(&iterator1);
            node2 = next(&iterator2);
        }
    }
    return count;
}

Here is the fix for the search function (see above comments):

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

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

Don't forget to initialise secondTree = NULL in main, and to free the memory used by your trees (I'll leave that for you to take care of).

Answered By - trincot

Answer Checked By - Willingham (WPSolving Volunteer)