#!/usr/bin/perl -lw
use strict;
use List::Util qw[ sum shuffle ];
use Benchmark qw[ cmpthese ];
use Devel::Size qw[ total_size ];

my $MAX = 10000;
our @array = 1 .. $MAX;
our $tree = make_tree($MAX/2,undef,undef);

$tree = insert( $_, $tree) for shuffle 1 .. $MAX;

print "Array[ 1..$MAX]: ", total_size( \@array );
print "Sum \@array = ", sum( @array );
print "Tree[ 1..$MAX ]: ", total_size( $tree );
print "Sum tree = ", sum_tree( $tree );

cmpthese -1, {
    tree => q[ my $sum = sum_tree( $tree ); ],
    array=> q[ my $sum = sum @array ],
};

exit;

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] }