# binary-trees Python 3 program

## source code

```# The Computer Language Benchmarks Game
# https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
#
# contributed by Antoine Pitrou
# modified by Dominique Wahli and Daniel Nanz
# modified by Joerg Baumann

import sys
import multiprocessing as mp

def make_tree(d):

if d > 0:
d -= 1
return (make_tree(d), make_tree(d))
return (None, None)

def check_tree(node):

(l, r) = node
if l is None:
return 1
else:
return 1 + check_tree(l) + check_tree(r)

def make_check(itde, make=make_tree, check=check_tree):

i, d = itde
return check(make(d))

def get_argchunks(i, d, chunksize=5000):

assert chunksize % 2 == 0
chunk = []
for k in range(1, i + 1):
chunk.extend([(k, d)])
if len(chunk) == chunksize:
yield chunk
chunk = []
if len(chunk) > 0:
yield chunk

def main(n, min_depth=4):

max_depth = max(min_depth + 2, n)
stretch_depth = max_depth + 1
if mp.cpu_count() > 1:
pool = mp.Pool()
chunkmap = pool.map
else:
chunkmap = map

print('stretch tree of depth {0}\t check: {1}'.format(
stretch_depth, make_check((0, stretch_depth))))

long_lived_tree = make_tree(max_depth)

mmd = max_depth + min_depth
for d in range(min_depth, stretch_depth, 2):
i = 2 ** (mmd - d)
cs = 0
for argchunk in get_argchunks(i,d):
cs += sum(chunkmap(make_check, argchunk))
print('{0}\t trees of depth {1}\t check: {2}'.format(i, d, cs))

print('long lived tree of depth {0}\t check: {1}'.format(
max_depth, check_tree(long_lived_tree)))

if __name__ == '__main__':
main(int(sys.argv[1]))
```

## notes, command-line, and program output

```NOTES:
Python 3.8.0

Mon, 28 Oct 2019 00:16:01 GMT

MAKE:
mv binarytrees.python3 binarytrees.py
mypy .
Success: no issues found in 1 source file

5.88s to complete and log all make actions

COMMAND LINE:
/opt/src/Python-3.8.0/bin/python3 -OO binarytrees.py 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303
```