1. Give the declaration of a Binary Search Tree of integers ($$\texttt{BST}$$).
2. Write a recursive function that checks whether an element belongs to a $$\texttt{BST}$$.
3. Write an iterative function that checks whether an element belongs to a $$\texttt{BST}$$.
4. Given 2 $$\texttt{BST}$$s, and using the above written function, write a function that checks whether the elements of both $$\texttt{BST}$$s are the same or not. The time complexity of your algorithm should be \(\texttt{O(m} \times \texttt{n)}\), where $$\texttt{m}$$ and $$\texttt{n}$$ are the numbers of elements in the two $$\texttt{BST}$$s.
5. Knowing that the inorder traversal of $$\texttt{BST}$$s produces sorted lists, rewrite the previous function in such a way that the time complexity of your algorithm should be $$\texttt{O(min(m, n))}$$.

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 belongi(Btree B, element e)
{
	while (B)
	{
		if (B->data == e) return 1;
		if (B->data > e) B=B->left;
		else B=B->right;
	}
	return 0;
}

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

int samei(Btree A, Btree B)
{
	stack s1 = CreateStack();
	stack s2 = CreateStack();
	int done1 = 0;
	int done2 = 0;
	int v1, v2;

	while (!done1 && !done2)
	{
		while (!done1)
		{
			if (A)
			{
				Push(&s1, A);
				A = A->left;
			}
			else
			{
				if (Top(s1, &A))
				{
					Pop(&s1);
					v1 = A->data;
					A = A->right;
					break;
				}
				else
					done1 = 1;
			}
		}

		while (!done2)
		{
			if (B)
			{
				Push(&s2, B);
				B = B->left;
			}
			else
			{
				if (Top(s2, &B))
				{
					Pop(&s2);
					v2 = B->data;
					B = B->right;
					break;
				}
				else
					done2 = 1;
			}
		}

		if (done1 == 1 && done2 == 1)
			return 1;
		if (v1 != v2) return 0;

		done1 = 0;
		done2 = 0;
	}
}