I'll come in at 153 characters. I'm sure it has to be better than that ... I'm using too many temp vars.

Updated: Forgot to change my datastructure from a hash of hashes to a hash of arrays. That caused the bug jarich noticed. ++!

#!/usr/local/bin/perl

my %tree = (
    'larger than a breadbox' => [
        'cat',
        'giraffe',
    ],
);

sub a {
    print 'Is your animal ', shift, "?\n";
    my $answer = <STDIN>;
    chomp $answer;
    return 1 if $answer =~ /y/i;
    return 0;
}

sub t {
    print "What is your animal?\n";
    my $answer = <STDIN>;
    chomp $answer;
    return $answer;
}

sub i {
    my ($g, $u) = @_;
    print "What is a question that is true for $u, but false for $g?\n
+";
    my $answer = <STDIN>;
    chomp $answer;
    $answer =~ s/Is your animal //;
    return $answer;
}

sub w {
    print "Do you want to continue?\n";
    my $answer = <STDIN>;
    chomp $answer;
    return 1 if $answer =~ /y/i;
    return 0;
}

#234567890#234567890#234567890#234567890#234567890#234567890#234567890
+#234567890
sub f {
($s,%t)=@_;$q=$s;do{{$v=a($q);$a=$t{$q}[$v];$q=$a,redo if$t{$a};$q=$s,
+next if a(
$a);$n=&t;$o=i($a,$n);$t{$o}=[$t{$q}[$v],$n];$t{$q}[$v]=$o;$q=$s}}whil
+e&w
}

f( 'larger than a breadbox',%tree);

__END__
[download]

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.