#include <stdio.h>
#include <stdlib.h>

struct node
{
	int data;
	struct node *left;
	struct node *right;
};

node *new_node()
{
	node *n = (node *) malloc(sizeof(node));
	n->left = n->right = NULL;
	return n;
}

void insert(node **root, int data)
{
	if(!*root) *root = new_node();
	if(!(*root)->data) (*root)->data = data;
	else if(data < (*root)->data) insert(&(*root)->left, data); else insert(&(*root)->right, data);
}

void inorder(node *root)
{
	if(root==NULL) return;
	inorder(root->left);
	printf("%2d ", root->data);
	inorder(root->right);
}

void preorder(node *root)
{
	if(root==NULL) return;
	printf("%2d ", root->data);
	preorder(root->left);
	preorder(root->right);
}

void postorder(node *root)
{
	if(root==NULL) return;
	postorder(root->left);
	postorder(root->right);
	printf("%2d ", root->data);
}

void free_tree(node *root)
{
	if(root==NULL) return;
	free_tree(root->left);
	free_tree(root->right);
	free(root);
}

int tree_minimum(node *n)
{
	while(n->left) n = n->left;
	return(n->data);
}

int tree_maximum(node *n)
{
	while(n->right) n = n->right;
	return(n->data);
}

int tree_minimum_recursive(node *n)
{
	if(!n->left) return(n->data);
	return(tree_minimum_recursive(n->left));
}

int tree_maximum_recursive(node *n)
{
	if(!n->right) return(n->data);
	return(tree_maximum_recursive(n->right));
}

int main(int argc, char *argv[])
{
	node *root = NULL;

	// generate a tree from (nice) example values
	int values[] = {17, 12, 10, 5, 15, 20, 19, 28, 33};
	for(unsigned int i = 0; i<sizeof(values)/sizeof(int); i++)
		insert(&root, values[i]);
	
	printf("Pre-Order:  ");
	preorder(root);
	printf("\nPost-Order: ");
	postorder(root);
	printf("\nIn-Order:   ");
	inorder(root);
	printf("\n");
	
	printf("Tree minimum: %2d (iterative), %2d (recursive)\n", tree_minimum(root), tree_minimum_recursive(root));
	printf("Tree maximum: %2d (iterative), %2d (recursive)\n", tree_maximum(root), tree_maximum_recursive(root));
	free_tree(root);
	return 0;
}