Drupal - Create taxonomy terms on the fly

Use the Hierarchical Select module:

Hierarchical Select has the ability to save the entire lineage of a selection or only the "deepest" selection. You can configure it to force the user to make a selection as deep as possible in the tree, or allow the user to select an item anywhere in the tree. Levels can be labeled, you can configure limit the number of items that can be selected, configure a title for the dropbox, choose a site-wide animation delay, and so on. You can even create new items and levels through Hierarchical Select!

Another way is selecting Autocomplete term widget (tagging) as field widget, when creating your term reference field

As another option, there is the Simple hierarchical select module.

 //see if this term already exists and fetch it if it does
  $term = taxonomy_get_term_by_name($i);

  //if it doesn't exist, make it
  if ($term == array()){
    //make a new class to hold the term for taxonomy 1
    $taxonomy = new stdClass();
    $taxonomy->name = $i;
    // mentioned vid here as of now i placed 1.
    $taxonomy->vid = 1;
    taxonomy_term_save($taxonomy);
    //now fetch it so we have it's tid
    $term = taxonomy_get_term_by_name($i);
  }

  //set $tid as it's returned from  taxonomy_get_term_by_name
  $tid = key($term);

  //tag the node with the appropriate tag
   $node->field_tags['und'][0] = array('tid' => $tid);

  //save the tagged node
  node_save($node);
  $i++;

Above code will check for term exist and if not creates new term, when creating new content.