#!/usr/bin/perl -w
use strict;
use Data::Dumper;

my $MAX = 10000;
my $tree = make_tree($MAX/2,undef,undef);

for(my $x=1;$x<$MAX;$x++)
{
    $tree = insert(int(rand($MAX)), $tree);
}

print "sum = ", sum_tree($tree), "\n";
#print Dumper $tree;

sub sum_tree
{
    my $tree = shift;
   
    return 0 if not defined($tree);
    return node($tree) + sum_tree(right($tree)) + sum_tree(left($tree));
}

sub insert
{
    (my $elem, my $tree) = @_;

    if(not defined($tree)){ return make_tree($elem, undef, undef); }
    
    my $curr = node($tree);
    if( $elem == $curr) { return $tree; }
    elsif($elem < $curr)
    {
        return make_tree($curr,
                         insert($elem,left($tree)),
                         right($tree));
    }
    elsif($elem > $curr)
    {
        return make_tree($curr,
                         left($tree),
                         insert($elem,right($tree)));
    }
}

sub make_tree { [$_[0], $_[1], $_[2]] }
sub node  { $_[0]->[0] }
sub left  { $_[0]->[1] }
sub right { $_[0]->[2] }