#include <stdio.h>
#include <malloc.h>
#include "/home/comp320/public_html/2005/assignments/support/320bool.h"

/*******************
 * Binary Tree Type
 *******************/
enum ABTree_Tag {IS_LEAF, IS_NODE};
struct ABTree {
    enum ABTree_Tag  tag;
    union {
	int  leaf;
	struct {
	    struct ABTree *  left;
	    struct ABTree *  right;
	} node;
    } elt;
};
typedef  struct ABTree *  BTree;

/*******************
 * Binary Tree Constructor Helper
 *******************/

/* Allocate one BTree structure and check for correct allocation.
 */
BTree
malloc_BTree()
{
    BTree tree = (BTree) malloc(sizeof(struct ABTree));

    if (tree == NULL) {
	fprintf(stderr,
		"malloc_BTree: Unable to allocate space for tree node.\n");
	exit(1);
    }

    return tree;
}

/*******************
 * Binary Tree Constructors
 *******************/
BTree
make_leaf(int leaf)
{
    BTree tree = malloc_BTree();
    tree->tag      = IS_LEAF;
    tree->elt.leaf = leaf;

    return tree;
}

BTree
make_node(BTree left, BTree right)
{
    BTree tree = malloc_BTree();
    tree->tag            = IS_NODE;
    tree->elt.node.left  = left;
    tree->elt.node.right = right;

    return tree;
}

/*******************
 * Binary Tree Basic Helper Functions
 *******************/

/* Assert that this node of the tree structure is valid.
 */
void
assert_valid_BTree(BTree tree)
{
    if (tree == NULL) {
	fprintf(stderr,"Invalid tree.\n");
	exit(1);
    }
}

/*******************
 * Binary Tree Basic Predicates
 *******************/
bool
is_leaf(BTree tree)
{
    assert_valid_BTree(tree);
    return (tree->tag == IS_LEAF);
}

bool
is_node(BTree tree)
{
    assert_valid_BTree(tree);
    return (tree->tag == IS_NODE);
}

/*******************
 * Binary Tree Selectors
 *******************/
int
tree_leaf(BTree tree)
{
    if (is_leaf(tree))
	return tree->elt.leaf;
    else {
	fprintf(stderr,"Tree isn't a leaf.\n");
	exit(1);
    }
}

BTree
tree_left(BTree tree)
{
    if (is_node(tree))
	return tree->elt.node.left;
    else {
	fprintf(stderr,"Tree isn't a node.\n");
	exit(1);
    }
}

BTree
tree_right(BTree tree)
{
    if (is_node(tree))
	return tree->elt.node.right;
    else {
	fprintf(stderr,"Tree isn't a node.\n");
	exit(1);
    }
}


/*******************
 * Binary Tree Functions
 *******************/

/* Returns the sum of all the numbers in the input tree.
 */
int
sum_tree(BTree tree)
{
    assert_valid_BTree(tree);
    if (is_leaf(tree))
	return tree_leaf(tree);
    else
	return sum_tree(tree_left(tree)) + sum_tree(tree_right(tree));
}

/* Prints the tree to a single line of standard output.
 * Groups nodes' children in parentheses, with nodes separated by spaces.
 */
void
print_tree(BTree tree)
{
    assert_valid_BTree(tree);
    if (is_leaf(tree))
	printf("%d",tree_leaf(tree));
    else {
	printf(" (");
	print_tree(tree_left(tree));
	printf(" ");
	print_tree(tree_right(tree));
	printf(") ");
    }
}


/*******************
 * Main function to print the sample tree and its sum.
 *******************/
int
main(void)
{
    BTree  tree = make_node(make_leaf(3),
			    make_node(make_node(make_leaf(2),
						make_leaf(7)),
				      make_leaf(9)));

    printf("The sum of the elements in\n");
    print_tree(tree);
    printf("\nis %d.\n",sum_tree(tree));

    return 0;  /* no error */
}


A Part Of Thiyagaraaj Websites