## Binary Trees

### Binary Trees Euphoria

```-- The Computer Language Shootout Benchmarks
--  http://shootout.alioth.debian.org/
--
--  Converted to Euphoria by Jason Gade
--  run: exu binary-trees.ex [N=0]

without warning
without type_check

include std/get.e

constant LEFT =  1,
RIGHT = 2,
ITEM =  3

constant NULL = {}

function ItemCheck(sequence tree)

if equal(tree[LEFT], NULL) then
return tree[ITEM]
else
return tree[ITEM] + ItemCheck(tree[LEFT]) - ItemCheck(tree[RIGHT])

end if

end function -- ItemCheck

function BottomUpTree(atom item, integer depth)

if depth > 0 then
return {BottomUpTree(2 * item - 1, depth - 1),
BottomUpTree(2 * item, depth - 1),
item}
else
return {NULL, NULL, item}

end if
end function -- BottomUpTree

procedure main(sequence argv)

atom iterations, check
integer minDepth, maxDepth, stretchDepth
sequence stretchTree, longLivedTree, tempTree
object N

if length(argv) >= 3 then
N = value(argv[3])
N = N[2]
else
N = 0
end if

minDepth = 4

if (minDepth + 2) > N then
maxDepth = minDepth + 2
else
maxDepth = N
end if

stretchDepth = maxDepth + 1

stretchTree = BottomUpTree(0, stretchDepth)
printf(1, "stretch tree of depth %d\t  check: %d\n",
{stretchDepth,
ItemCheck(stretchTree)})

stretchTree = {}

longLivedTree = BottomUpTree(0, maxDepth)

for depth = minDepth to maxDepth by 2 do

iterations = power(2, maxDepth - depth + minDepth)

check = 0

for i = 1 to iterations do

tempTree = BottomUpTree(i, depth)
check += ItemCheck(tempTree)
tempTree = {}

tempTree = BottomUpTree(-i, depth)
check += ItemCheck(tempTree)
tempTree = {}

end for -- i

printf(1, "%d\t  trees of depth %d\t  check: %d\n",
{iterations * 2, depth, check })

end for -- depth

printf(1, "long lived tree of depth %d\t  check: %d\n",
{maxDepth, ItemCheck(longLivedTree)})

end procedure -- main

main(command_line())
```

### Binary Trees Python

```# The Computer Language Benchmarks Game
# http://shootout.alioth.debian.org/
#
# contributed by Antoine Pitrou
# modified by Dominique Wahli
# modified by Heinrich Acker

import sys

def make_tree(item, depth):
if not depth: return item, None, None
item2 = item + item
depth -= 1
return item, make_tree(item2 - 1, depth), make_tree(item2, depth)

def check_tree((item, left, right)):
if not left: return item
return item + check_tree(left) - check_tree(right)

min_depth = 4
max_depth = max(min_depth + 2, int(sys.argv[1]))
stretch_depth = max_depth + 1

print "stretch tree of depth %d\t check:" % stretch_depth, check_tree(make_tree(0, stretch_depth))

long_lived_tree = make_tree(0, max_depth)

iterations = 2**max_depth
for depth in xrange(min_depth, stretch_depth, 2):

check = 0
for i in xrange(1, iterations + 1):
check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth))

print "%d\t trees of depth %d\t check:" % (iterations * 2, depth), check
iterations /= 4

print "long lived tree of depth %d\t check:" % max_depth, check_tree(long_lived_tree)

```

### Binary Trees Perl

```# The Computer Language Benchmarks Game
# http://shootout.alioth.debian.org/
#
# contributed by Emanuele Zeppieri

sub bottomup_tree {
my (\$value, \$depth) = @_;
return \$value unless \$depth;
my \$value2 = \$value * 2; \$depth--;
[ bottomup_tree(\$value2-1, \$depth), bottomup_tree(\$value2, \$depth), \$value ]
}

sub check_tree {
my (\$left, \$right, \$value) = @{ \$_[0] };
\$value + (
ref \$left ? check_tree(\$left) - check_tree(\$right) : \$left - \$right
)
}

my \$max_depth = shift @ARGV;
my \$min_depth = 4;

\$max_depth = \$min_depth + 2 if \$min_depth + 2 > \$max_depth;

my \$stretch_depth = \$max_depth + 1;
my \$stretch_tree = bottomup_tree(0, \$stretch_depth);
print "stretch tree of depth \$stretch_depth\t check: ",
check_tree(\$stretch_tree), "\n";
undef \$stretch_tree;

my \$longlived_tree = bottomup_tree(0, \$max_depth);

for ( my \$depth = \$min_depth; \$depth <= \$max_depth; \$depth += 2 ) {
my \$iterations = 2 << \$max_depth - \$depth + \$min_depth - 1;
my \$check = 0;

foreach (1..\$iterations) {
\$check += check_tree( bottomup_tree(0, \$depth) );
\$check += check_tree( bottomup_tree(0, \$depth) )
}

print 2*\$iterations, "\t trees of depth \$depth\t check: ", \$check, "\n"
}

print "long lived tree of depth \$max_depth\t check: ",
check_tree(\$longlived_tree), "\n"

```