#include <stdio.h>

struct tree_node {
	int value;
	struct tree_node * left;
	struct tree_node * right;
};

typedef struct tree_node Node;

void init( Node ** node, int n ) {
	*node = malloc( sizeof( Node ) );
	(*node) -> value = n;

	(*node) -> left =  NULL;
	(*node) -> right = NULL;
}

/* we may have to change the value of root,
 * so therefore we pass the address of the
 * root
 */

void insert( Node ** root, int n ) {
	/* deal with the special case */

	if ( *root == NULL ) {
		init( root, n );
		return;
	}

	Node * ptr = *root;

	while( 1 ) {
		if ( n < ptr -> value ) {
			if ( ptr -> left == NULL ) {
				init( &(ptr -> left), n );

				return;
			} else {
				ptr = ptr -> left;
			}
		} else if ( n > ptr -> value ) {
			if ( ptr -> right == NULL ) {
				init( &(ptr -> right), n );

				return;
			} else {
				ptr = ptr -> right;
			}
		}
	}
}

void traversal_rec( Node * node, int which ) {
	if ( which == -1 ) {
		printf( "%3d ", node -> value );
	}

	if ( node -> left != NULL ) {
		traversal_rec( node -> left, which );
	}

	if ( which == 0 ) {
		printf( "%3d ", node -> value );
	}

	if ( node -> right != NULL ) {
		traversal_rec( node -> right, which );
	}

	if ( which == 1 ) {
		printf( "%3d ", node -> value );
	}
}

void traversal( Node * root, int which ) {
	if ( root == NULL ) {
		return;
	}

	traversal_rec( root, which );

	printf( "\n" );
}

void clean_rec( Node * node ) {
	if ( node -> left != NULL ) {
		clean_rec( node -> left );
	}

	if ( node -> right != NULL ) {
		clean_rec( node -> right );
	}

	free( node );
}

void clean( Node * root ) {
	if ( root == NULL ) {
		return;
	}

	clean_rec( root );
}

int main() {
	Node * root;

	int i;

	printf( "Adding:     " );

	for ( i = 1; i < 15; ++i ) {
		int val = 59*i % 167;
		printf( "%3d ", val );
		insert( &root, val );
	}

	printf( "\n" );

	printf( "Pre-order:  " );
	traversal( root, -1 );

	printf( "In-order:   " );
	traversal( root,  0 );

	printf( "Post-order: " );
	traversal( root,  1 );

	clean( root );

	return 0;
}