How can I check if two binary trees contain the same nodes?

Question

I am trying the implement a function which checks whether two binary search trees are equal, order of the nodes not matter. But my implementation does not work.

I am not allowed to flatten the trees into arrays.

this is what I have so far:

int isIdentical(struct Node* root1, struct Node* root2)
{
    
    if (root1 == NULL && root2 == NULL)
        return 1;
    
    else if (root1 == NULL || root2 == NULL)
        return 0;
    else { 
        if (root1->data == root2->data && isIdentical(root1->left, root2->left)
            && isIdentical(root1->right, root2->right))
            return 1;
        else
            return 0;
    }
}

when supplied with trees containing the nodes tree A = 2 4 5 6 and Tree B = 2 5 4 6, the output should be:

1, meaning they are equal, but instead I am getting 0. I am not sure where I am going wrong.

This is how Node is implemeted:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

Answer 1

Make a recursive function that traverses treeA and checks that every item is present in treeB. On failure it abandons the search and returns 0 for failure. It can be your function

int isIdentical(struct Node* root1, struct Node* root2)

If success, call the function again with the arguments for treeA and treeB reversed. The 'check if present' operation can be iterative and inline, because it does not need to backtrack.

Example untried code, to give the idea.

int isAllFound(struct Node* root1, struct Node* root2)
{
    // recursive parse of tree 1
    if (root1 == NULL)
        return 1;
    
    // iterative search of tree 2
    int found = 0;
    struct Node *root = root2;
    while(root != NULL) {
        if(root1->data == root->data) {
            found = 1;
            break;
        }
        if(root1->data < root->data)
            root = root->left;
        else
            root = root->right;
    }
    if(!found)
        return 0;
    
    // continue recursive parse of tree 1
    if(!isAllFound(root1->left, root2))
        return 0;
    if(!isAllFound(root1->right, root2))
        return 0;
    return 1;
}

Then call like

if(isAllFound(treeA, treeB) && isAllFound(treeB, treeA))
    puts("Success!");

If every item of treeA can be found in treeB, and every item of treeB can be found in treeA then they contain the same data. Provided the keys are unique.