Comparing nodes of two BSTs in C++

Question

I need to compare each node of one BST with all the nodes of another BST.

Similar to how you'd do comparison in an array:

string arr[10];
string arr2[10];

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        compare(arr[j], arr2[i]);
    }
}

but instead of the outer for loop you're traversing in bst1, and instead of the inner for loop, you're traversing in bst2. then comparing node of bst1 with all nodes of bst2, then moving on to the next node of bst1 and comparing that with all of bst2 and so on

Can't seem to wrap my head around how to implement the traversals. Any help would be appreciated

Answer 1

The idea is to call traverse on the root node of Tree1 and for each node in it, pass it to another function compare which is called on root node of Tree2 and compares the passed node with every node in it.

#include <iostream>

struct Node
{
    int val;
    Node *left, *right;
};

void compare(Node *curr2, Node *curr1)
{
    if (curr2 == nullptr)
        return;

    compare(curr2->left, curr1);
    if (curr2->val == curr1->val)       // replace with your comparison function
        cout << "Match found for " << curr1->val << endl;
    compare(curr2->right, curr1);
}

void traverse(Node *curr1, Node *root2)
{
    if (curr1 == nullptr)
        return;

    traverse(curr1->left, root2);
    compare(root2, curr1);
    traverse(curr1->right, root2);
}

int main()
{
    Node *root1, *root2;
    traverse(root1, root2);
}