**Problem : **
Recall from that it is possible to represent arithmetic, parenthesized
expressions using a tree. If a node is an operator, such as a plus or
a division sign, each of the children must be either a number, or another
expression. In other words, the two children of an operator will be its
operands.
+
3 4
The above means (3+4).
Write a function which will take in a `tree_t` of the form:

typedef struct _tree {
char op;
int value;
struct _tree *left, *right;
} tree_t;

and will evaluate the tree according to the above specification that the
children of an operator will evaluate to numbers. The

`op` field will be
one of the following values, '+' '-', '*', '/', or '_', which are sharp
defined to be ADD, SUB, MULT, DIV, and EMPTY respectively. Assume that
the tree is a well formed expression (you don't need to do any error checking).

int eval (tree_t *t)
{
/* Although a NULL tree is invalid, we will check for it
* any way and assign it a value of 0.
*/
if (t == NULL) return 0;
/* If there is no operator, the tree is the value in it */
if (t->op == EMPTY) return t->value;
/* Otherwise, the tree evaluates to performing the operation
* on the evaluation of its subtrees, the operands.
*/
switch (t->op) {
case ADD: return eval(t->left) + eval(t->right);
case SUB: return eval(t->left) - eval(t->right);
case MULT: return eval(t->left) * eval(t->right);
case DIV: return eval(t->left) / eval(t->right);
}
}

**Problem : **
Assume now that your nodes represent people and their ages and as a result
have fields for a person's name and age. Use the following definition for
`tree_t`:

typedef struct _tree {
int age;
char *name;
struct _tree *left, *right;
} tree_t;

Write a single function which will take in a pointer to a

`tree_t` and
will free the entire tree and all of the memory associated with it.

void free_tree (tree_t *t)
{
/* Base case */
if (t == NULL) return;
/* Recursive calls */
free_tree (t->left);
free_tree (t->right);
/* The space for the name is dynamic and must be freed as well */
free (t->name);
/* Finally free the memory for the individual node */
free (t);
}

**Problem : **
A Huffman tree is a means of encoding characters, that is, a way of
assigning a certain sequence of bits to a character (ASCII is another
convention). The idea is that you can save space when storing a file if
you can find an encoding for the characters such that the file requires
fewer bits overall. We will not cover the process of building such a tree,
but we will consider the process of using one. Starting from the root
node, you keep walking along either the left or the right branch until you
reach the desired character. Moving left corresponds to a 0 bit and moving
right to a 1 bit. So, if you have to go left, right, right to get to the
character 'A', then the encoding for 'A' is 011.
How can you describe the location of all of the nodes that have characters
associated with them? The root node, for example, has no character associated
with it.

The decoding (translation from bits into characters) using a Huffman tree
relies on the fact that the encoding of one character is never the prefix
of another character. For example, if one character is encoded with the
bits '011', then the encodings for all of the other characters cannot start
with those same three bits. If there were such a case, then when decoding
the bits, it would be ambiguous as to which character was encoded. In terms
of the tree this means that there can be no character node which has children;
all of the nodes associated with characters must be leaves.