Given 2 BSTs, write a recursive function that checks whether the elements of both BSTs are the same or not. The time complexity of your algorithm should be \(O(m\times n)\), where \(m\) and \(n\) are the numbers of elements in the two BSTs .


Difficulty level
This exercise is mostly suitable for students
typedef struct node
{
	element data;
	struct node *left, *right;
} *Btree;


int belongr(Btree B, element e)
{
	if (!B) return 0;
	if (B->data == e) return 1;
	if (B->data > e) return belongr(B->left, e);
	return belongr(B->right, e);
}


int belong(Btree A, Btree B)
{
	if (!A) return 1;
	if (!belongr(B, A->data)) return 0;
	return belong(A->left, B) && belong(A->right, B);
}

int same(Btree A, Btree B)
{
	return belong(A, B) && belong(B, A);
}

Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Checking whether elements of 2 BSTs are the same using an iterative function