# Binary Trees

Coding challenges are a great resource for learning coding techniques and improve analytical thinking, this is a collection of challenges from different platforms.

See the challenge description.

## Usage

``````\$ go build -o solution main.go

\$ echo 10 | ./solution
``````

## Sample

input00.txt
``````10
``````
output00.txt
``````stretch tree of depth 11	 check: 4095
1024	 trees of depth 4	 check: 31744
256	 trees of depth 6	 check: 32512
64	 trees of depth 8	 check: 32704
16	 trees of depth 10	 check: 32752
long lived tree of depth 10	 check: 2047
``````

## Solution

This solution is not fully compliant to the challenge rules, I just wanted to learn about profiling Go programs and tweak them to run as fast as its C and Rust counter-parts (and indeed it is faster).

`main.go`
``````package main

import (
"fmt"
"os"
"runtime/pprof"
"sync"
)

func main() {
if cpup := os.Getenv("CPUPROFILE"); cpup != "" {
f, err := os.Create(cpup)
if err != nil {
fmt.Fprintf(os.Stderr, "Can't create CPU profile file: %v", err)
os.Exit(1)
}

defer f.Close()

if err := pprof.StartCPUProfile(f); err != nil {
fmt.Fprintf(os.Stderr, "Can't profile CPU usage: %v", err)
os.Exit(1)
}

defer pprof.StopCPUProfile()
}

min := 4
var max int
fmt.Scan(&max)

if max < min+2 {
max = min + 2
}

{
st := NewTree(max + 1)
fmt.Printf("stretch tree of depth %d\t check: %d\n", max+1, st.Check())
}

llt := NewTree(max)

var wg sync.WaitGroup
msgs := make([]string, max+1)

for cd := min; cd <= max; cd += 2 {

go func(cd int) {
defer wg.Done()

pool := NewPool(cd)
n := 1 << (max - cd + min)
i := 0
sum := 0

for ; i < n; i++ {
t := NewTreeWithPool(cd, pool)
sum += t.Check()
}

msgs[cd] = fmt.Sprintf("%d\t trees of depth %d\t check: %d", i, cd, sum)
}(cd)
}

wg.Wait()

for cd := min; cd <= max; cd += 2 {
fmt.Println(msgs[cd])
}

fmt.Printf("long lived tree of depth %d\t check: %d\n", max, llt.Check())

if memp := os.Getenv("MEMPROFILE"); memp != "" {
f, err := os.Create(memp)
if err != nil {
fmt.Fprintf(os.Stderr, "Can't create memory profile file: %v", err)
os.Exit(1)
}

defer f.Close()

if err := pprof.WriteHeapProfile(f); err != nil {
fmt.Fprintf(os.Stderr, "Can't profile memory usage: %v", err)
os.Exit(1)
}
}
}

type Tree struct {
left, right *Tree
}

func NewTree(d int) Tree {
return NewTreeWithPool(d, NewPool(d))
}

func NewTreeWithPool(d int, pool []Tree) Tree {
if d < 1 {
return Tree{}
}

base := 1 << d
total := base<<1 - 2
pool = pool[:0]

for i := 0; i < base; i++ {
pool = append(pool, Tree{})
}

for i := 0; i < total-2; i += 2 {
pool = append(pool, Tree{&pool[i], &pool[i+1]})
}

return Tree{&pool[total-2], &pool[total-1]}
}

func (t *Tree) Check() int {
if t.left != nil {
return t.left.Check() + t.right.Check() + 1
}

return 1
}

func NewPool(d int) []Tree {
total := 1<<(d+1) - 2
return make([]Tree, total)
}
``````