#!perl
($f,$s)=@ARGV;$t=e($f,$s,length($f));p($t);print"
";sub e{my($i,$c,$d,$p,$r,$g,$h);my($k,$l,$m)=@_;return 0if($m<=0);$p->{V}=substr($l,0,1);$p->{L}=0;$p->{R}=0;return$p if($m==1);for($i=0;substr($k,$i,1)ne substr($l,0,1);$i++){}$c=$m-$i-1;$d=$m-$c-1;$g=substr($l,1);$r=$d+1;$h=substr($k,$r);if (!$g){$p->{L}=0;}else{$p->{L}=e($k,$g,$d);}if (!$h){$p->{R}=0;}else{$p->{R}=e($h,substr($l,$r),$c);}return $p}sub p{my($y)=@_;return unless $y;p($y->{L});p($y->{R});print $y->{V};}

#!perl -w
# bintree - binary tree demo program


use strict;
my($f, $s, $i, $root, $two);
  
#print "\n\n-----------------\nProgram Start\n-----------------\n";

($f,$s)=@ARGV;

#print "length f=", length($f), "\n";
for ($i=0; $i{VALUE}=substr($pre, 0, 1);
    #print "value=", substr($pre, 0, 1), "\n";
    $p->{LEFT}=undef;
    $p->{RIGHT}=undef;
    
    if ($len == 1)
    {
	return $p;
    }
    
    for ($i=0; substr($in, $i, 1) ne substr($pre, 0, 1); $i++)
    {
    }
    
    $lenright=$len-$i-1;
    $lenleft=$len-$lenright-1;
    #print "i=", $i, "\n";
    #print "lenleft=", $lenleft, "\n";
    #print "lenright=", $lenright, "\n";
    #print "substr1=", 
    $aa=substr($pre, 1);
    if (!$aa)
    {
	#print ("AA NULL\n");
    }
    
    #print "substr2=", 
    $bb=substr($in, $lenleft+1);

    if (!$aa)
    {
	$p->{LEFT}=undef;
    }
    else
    {
	#print "LEFT LEFT LEFT LEFT LEFT\n";
	$p->{LEFT}=buildtree($in, substr($pre, 1), $lenleft);
    }
    $r=$lenleft+1;

    if (!$bb)
    {
	$p->{RIGHT}=undef;
    }
    else
    {
	$p->{RIGHT}=buildtree(substr($in, $r), substr($pre, $r),  $lenright);
    }
    return $p;
}
#      insert($root, $pre[0]);
#      if ($len==1)
#  	return p;
#      for ($i=0; $in[$i]!=$pre[0]; $i++);
#      $lenright=$len-$i-1;
#      $lenleft= $len-$lenright-1;
#      insert(p->left, buildtree(in, pre+1, lenleft));
#      insert(p->left, buildtree(in, pre+1, lenleft));
#      return p;
#  }

# $_[0] is the inorder string
# $_[1] is the preorder string
# $_[2] is the length of the string

#  sub buildtree {
#      my ($i, $lenright, $lenleft, $p);
#      insert($root, $pre[0]);
#      if ($len==1)
#  	return p;
#      for ($i=0; $in[$i]!=$pre[0]; $i++);
#      $lenright=$len-$i-1;
#      $lenleft= $len-$lenright-1;
#      insert(p->left, buildtree(in, pre+1, lenleft));
#      insert(p->left, buildtree(in, pre+1, lenleft));
#      return p;
#  }
     
    


#  use strict;
#  my($root, $n);

#  # first generate 20 random inserts
#  while ($n++ < 20) { insert($root, int(rand(1000)))}

#  # now dump out the tree all three ways
#  print "Pre order:  ";  pre_order($root);  print "\n";
#  print "In order:   ";  in_order($root);   print "\n";
#  print "Post order: ";  post_order($root); print "\n";

#  # prompt until EOF
#  for (print "Search? "; <>; print "Search? ") { 
#      chomp;
#      my $found = search($root, $_);
#      if ($found) { print "Found $_ at $found, $found->{VALUE}\n" }
#      else        { print "No $_ in tree\n" }
#  }

#  exit;

#########################################

# insert given value into proper point of
# provided tree.  If no tree provided, 
# use implicit pass by reference aspect of @_
# to fill one in for our caller.
sub insert {
    my($tree, $value, $position) = @_;  #position 0 means insert to left 1 right

    my($new);

#    $position=$three;
    print "value=", $value, "\n";
    print "position=", $position, "\n";

    unless ($tree) {
        $tree = {};                         # allocate new node
        $tree->{VALUE}  = $value;
        $tree->{LEFT}   = undef;
        $tree->{RIGHT}  = undef;
        $_[0] = $tree;              # $_[0] is reference param!
        return;
    }
    if ($position == 0) 
    {
	$new={};
        $new->{VALUE}  = $value;
        $new->{LEFT}  = $tree;
        $tree->{RIGHT}  = undef;

	#insert($tree->{LEFT},  $value, $position);
    }
    elsif ($position == 1) { 
	$new={};
        $new->{VALUE}  = $value;
        $new->{LEFT}  = undef;
        $tree->{RIGHT}  = $tree;
	#insert($tree->{RIGHT}, $value, $position);
    }
    else                            { warn "dup insert of $value\n"  }
                                    # XXX: no dups
}

# recurse on left child, 
# then show current value, 
# then recurse on right child.
sub in_order {
    my($tree) = @_;
    return unless $tree;
    in_order($tree->{LEFT});
    print $tree->{VALUE}, " ";
    in_order($tree->{RIGHT});
}

# show current value, 
# then recurse on left child, 
# then recurse on right child.
sub pre_order {
    my($tree) = @_;
    return unless $tree;
    print $tree->{VALUE}, " ";
    pre_order($tree->{LEFT});
    pre_order($tree->{RIGHT});
}

# recurse on left child, 
# then recurse on right child,
# then show current value. 
sub post_order {
    my($tree) = @_;
    return unless $tree;
    post_order($tree->{LEFT});
    post_order($tree->{RIGHT});
    print $tree->{VALUE};
}

# find out whether provided value is in the tree.
# if so, return the node at which the value was found.
# cut down search time by only looking in the correct
# branch, based on current value.
sub search {
    my($tree, $value) = @_;
    return unless $tree;
    if ($tree->{VALUE} == $value) {
        return $tree;
    }
    search($tree->{ ($value < $tree->{VALUE}) ? "LEFT" : "RIGHT"}, $value)
}