• Write a function that returns the level having the highest sum of its values.
    We assume that the root of the tree is at level 1, and that the tree is dynamically implemented.
  • Without performing any calculations, give the worst case time complexity of your function. Justify your answer.

For example, the third level of the following tree has the highest sum of values (sum=17).

     1
    / \
  2   3
 / \    \
4  5    8
   / \
  6  7


Difficulty level
This exercise is mostly suitable for students
The code was corrected by Ali Rida Younes

1* 

typedef struct {
	Btree tree;
	int level;
}elementq;

int highest_sum(Btree B)
{
	queue q;
	elementq e, el, er;
	int maxsum, currentsum, maxlevel, currentlevel;

	maxsum = maxlevel = INT_MIN;
	currentsum =0;
	currentlevel=1;
	q = CreateQueue();
	if (B)
	{
		e.tree = B;
		e.level = 1;
		EnQueue(&q,e );
		while (Front(q, &e))
		{
			DeQueue(&q);
			if (e.level > currentlevel) // new level
			{
				if (currentsum > maxsum)
				{
					maxsum = currentsum;
					maxlevel = currentlevel;
				}
				currentsum = e.tree->data;
				currentlevel = e.level;
			}
			else //same level
				currentsum += e.tree->data;

			if (e.tree->left)
			{
				el.level=e.level+1;
				el.tree = e.tree->left;
				EnQueue(&q, el);
			}
			if (e.tree->right)
			{
				er.level=e.level+1;
				er.tree = e.tree->right;
				EnQueue(&q, er);
			}
		}
	}
	if (currentsum > maxsum)
	{
		maxsum = currentsum;
		maxlevel = currentlevel;
	}
	return maxlevel;
}

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

Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Numerical value of a Polynomial