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

typedef struct node_t {
	char *string;
	struct node_t *left;
	struct node_t *right;
} node_t;

node_t *insert(node_t *root, node_t *new);
void print(node_t *root);
void dismantle(node_t *root);

int main()
{
	char line[256];
	node_t *root = NULL;	/* The tree is initially empty. */

	printf(
		"Press RETURN after each line,\n"
		"control-d after the RETURN after the last line.\n"
		"The lines will be output in alpahabetical order.\n"
	);

	while (gets(line) != NULL) {
		node_t *new = malloc(sizeof(node_t));
		if (new == NULL) {
			fprintf(stderr, "Can't malloc memory for node to hold \"%s\".", line);
			return EXIT_FAILURE;
		}

		new->string = malloc(strlen(line) + 1);
		if (new->string == NULL) {
			fprintf(stderr, "Can't malloc memory for \"%s\".\n", line);
			return EXIT_FAILURE;
		}
		strcpy(new->string, line);

		root = insert(root, new);
	}

	print(root);
	dismantle(root);
	return EXIT_SUCCESS;
}

node_t *insert(node_t *root, node_t *new)
{
	if (root == NULL) {
		/* Insert the new node into an empty tree. */
		root = new;
	}

	else if (strcmp(new->string, root->string) <= 0) {
		/* Insert the new node to the lower left of the root. */
		root->left = insert(root->left, new);
	}

	else {
		/* Insert the new node to the lower right of the root. */
		root->right = insert(root->right, new);
	}

	return root;
}

void print(node_t *root)     /* in order */
{
	if (root != NULL) {
		print(root->left);
		printf("%s\n", root->string);
		print(root->right);
	}
}

void dismantle(node_t *root)     /* post order */
{
	if (root != NULL) {
		dismantle(root->left);
		dismantle(root->right);

		free(root->string);
		free(root);
	}
}