/* mp5.c -- A solution written in C, using a binary tree */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* some test data */
const char const * mp5data = "fortnight.\n\0came \0eve"
                             "ry \0down \0bug \0A \0";

/* a lexicographically ordered binary tree of strings */
struct node { /* one tree node per string */
    struct node * left;
    struct node * right;
    const char * str;
};

struct node * tree; /* lexicographic dree of "words" */

void puttree( const char * s ) { /* sort s into the tree of strings */
    struct node * n; /* the new tree node */
    n = malloc( sizeof( struct node * ) );
    n->left = NULL;
    n->right = NULL;
    n->str = s;

    if (tree == NULL) { /* create tree */
	tree = n;
    } else { /* walk down tree looking where to put n */
        struct node * t = tree; /* place in tree, starts at root */
        for (;;) {
            if (strcmp( s, t->str ) >= 0) { /* right subtree */
		if (t->right == NULL) { /* found the place */
		    t->right = n;
		    break;
		}
		t = t->right; /* walk onward */
	    } else { /* left subtree */
		if (t->left == NULL) { /* found the place */
		    t->left = n;
		    break;
		}
		t = t->left; /* walk onward */
	    }
	}
    }
}

void printtree( struct node * t ) { /* traverse tree and print strings */
    if (t->left != NULL) printtree( t->left );
    fputs( t->str, stdout );
    if (t->right != NULL) printtree( t->right );
}

/* main program to sort and print mp5data */

int main() {
    const char * p = mp5data;
    for (;;) { /* loop exit is by break */
        int plen = strlen( p );

        if (strlen( p ) == 0) break;

	puttree( p );
	p = p + plen + 1;
    }
    printtree( tree );
}