• A binary tree is called \(\texttt{SumTree}\) if the value of each non-leaf node is equal to the sum of the nodes present in its left subtree and its right subtree.
  An empty tree is considered as a \(\texttt{SumTree}\) and the sum of an empty tree is equal to 0.
  Write a function that checks whether a binary tree is a \(\texttt{SumTree}\) or not.
• Without performing any calculations, give the worst case time complexity of your function. Justify your answer.

For example, the following binary trees are \(\texttt{SumTree}\)s.

    26
   /  \  
 10  3
 / \   \
4 6    3

     50
     /  \ 
   24   2
   /  \
 10   2
 /    /  \
5   1    1
  \
   5

1* 
int SumTree(Btree B)
{
	int sum = 0;
	return SumTree_helper(B, &sum);
}

int SumTree_helper(Btree B, int *sum)
{
	int l, r;
	if (B == NULL)
	{
		*sum = 0;
		return 1;
	}
	if (B->left == NULL && B->right == NULL)
	{
		*sum = B->data;
		return 1;
	}

	if (SumTree_helper(B->left, &l) == 1 && SumTree_helper(B->right, &r) == 1 && B->data == l + r)
	{
		*sum = 2* (l + r);
		return 1;
	}
	return 0;
}

2* n, where n is the number of elements in the tree.