We want to construct a binary search tree to represent a set of integer numbers. Unlike the traditional binary search tree where each node contains only one integer value, we want to allow each node to contain all the values between two bounds $$\texttt{[LowerBound, UpperBound]}$$. The bounds of the nodes do not intersect and are arranged in a way that for each node, the $$\texttt{UpperBound}$$ of its left node is less than its $$\texttt{LowerBound}$$, and its $$\texttt{UpperBound}$$ is less than the $$\texttt{LowerBound}$$ of its right node.

The values at each node are inserted in a non-ordered linked list.

Each value should not be present in a node more than once.

The below figure shows an example of this BST constructed from the set S = {-1250, -340, -459, -125, -50, -65, -20, -16, 25, 50, 65, -2, 0, 5, 2, 250, 500, 654} where the bounds are shown at each node.

You are asked to:

1. Propose a data structure that can represent this version of the binary search tree.
2. Write an iterative function that takes as parameter such a tree and a value $$v$$, searches and returns the node of the tree that contains that value or $$\texttt{Null}$$ if $$v$$ is not in the tree.
   Any helper function should be iterative too.
3. Give and discuss the complexity of your above written function(s).
4. Write a recursive function that takes as parameter such a tree, do an inorder traversal and prints on the screen the values of the nodes.
   Any helper function should be recursive too.
5. Give and discuss the complexity of your above written function(s).
6. Write a function that takes as parameter such a tree and a value $$v$$, adds $$v$$ in its appropriate place in the tree. Suppose the existence of a function that, for a given value, returns a lower bound and an upper bound values non encountered in the tree.

typedef struct {
	int lower, upper;
} interval;

typedef struct list {
	int data;
	struct list *next;
} *list;

typedef struct node {
	interval itv;
	list nbs;
	struct node *left, *right;
} *bst;

bst find(bst B, int value)
{
	list tmp;
	while (B)
	{
		if (value >= B->itv.lower && value <= B->itv.upper)
		{
			tmp = B->nbs;
			while (tmp)
			{
				if (tmp->data == value)
					return B;
				tmp = tmp->next;
			}
			return NULL;
		}
		else
			if (value < B->itv.lower)
				B = B->left;
			else
				B = B->right;
	}
	return NULL;
}

void print_list(list l)
{
	if (l)
	{
		printf("%d ", l->data);
		print_list( l->next);
	}
}

void inorder(bst B)
{
	if (B)
	{
		inorder(B->left);
		printf("\n");
		print_list(B->nbs);
		inorder(B->right);
	}
}

int addtolist(list *l , int value)
{
	if (*l == NULL)
	{
		*l = (list)malloc(sizeof(struct list));
		(*l)->data = value;
		(*l)->next = NULL;
		return 1;
	}
	if ((*l)->data == value)
		return 0;
	return  addtolist(&((*l)->next),  value);
}

int insert(bst *B, int value, int lower, int upper)
{
	if (*B == NULL)
	{
		*B = (bst)malloc(sizeof(struct node));
		(*B)->itv.lower = lower;
		(*B)->itv.upper = upper;
		(*B)->nbs = NULL;
		(*B)->left = (*B)->right = NULL;
		return addtolist(&((*B)->nbs), value);
	}
	if (value >= (*B)->itv.lower && value <= (*B)->itv.upper)
	{
		return addtolist(&((*B)->nbs), value);
	}
	if (value < (*B)->itv.lower)
		return insert(&((*B)->left), value, lower, upper);
	else
		return insert(&((*B)->right), value, lower, upper);
	 
}