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

struct node
{ char * data;
  struct node * left, * right; };

struct node * constr_node(char * s)
{ struct node * t = (struct node *)malloc(sizeof(struct node));
  t->data = s;
  t->left = NULL;
  t->right = NULL;
  return t; }

void print(struct node * t)
{ if (t == NULL)
    return;
  print(t->left);
  printf(" %s ", t->data);
  print(t->right); }

struct node * insert(struct node * t, char * s)
{ if (t == NULL)
    return constr_node(s);
  if (strcmp(s, t->data) < 0)
    t->left = insert(t->left, s);
  else
    t->right = insert(t->right, s);
  return t; }

int main()
{
  struct node * t6 = constr_node("zebra");
  struct node * t5 = constr_node("sean");
  t5->right = t6;
  struct node * t3 = constr_node("ant");
  struct node * t4 = constr_node("jay");
  struct node * t2 = constr_node("hello");
  t2->left = t3;
  t2->right = t4;
  struct node * t1 = constr_node("mug");
  t1->left = t2;
  t1->right = t5;
  print(t1); 

  while (1)
  { char word[100];
    printf("\n");
    gets(word);
    t1 = insert(t1, strdup(word));
    print(t1); }
}