// Week 14 – Solutions of the practice exercises
// Run: go run ./w14/exercises
package main

import (
	"fmt"
	"math"
)

type Node struct {
	Value       int
	Left, Right *Node
}

func leaf(v int) *Node { return &Node{Value: v} }

func sum(p *Node) int {
	if p == nil {
		return 0
	}
	return p.Value + sum(p.Left) + sum(p.Right)
}

func maxOf(p *Node) int {
	if p == nil {
		return math.MinInt
	}
	return max(p.Value, maxOf(p.Left), maxOf(p.Right))
}

func oneChild(p *Node) int {
	if p == nil {
		return 0
	}
	self := 0
	if (p.Left == nil) != (p.Right == nil) {
		self = 1
	}
	return self + oneChild(p.Left) + oneChild(p.Right)
}

func isFull(p *Node) bool {
	if p == nil {
		return true
	}
	if (p.Left == nil) != (p.Right == nil) {
		return false
	}
	return isFull(p.Left) && isFull(p.Right)
}

func level(p *Node, k int, out *[]int) {
	if p == nil {
		return
	}
	if k == 0 {
		*out = append(*out, p.Value)
		return
	}
	level(p.Left, k-1, out)
	level(p.Right, k-1, out)
}

func paths(p *Node, prefix string) {
	if p == nil {
		return
	}
	s := fmt.Sprint(p.Value)
	if prefix != "" {
		s = prefix + " -> " + s
	}
	if p.Left == nil && p.Right == nil {
		fmt.Println("   ", s)
	}
	paths(p.Left, s)
	paths(p.Right, s)
}

func same(a, b *Node) bool {
	if a == nil || b == nil {
		return a == b
	}
	return a.Value == b.Value && same(a.Left, b.Left) && same(a.Right, b.Right)
}

func build() *Node {
	return &Node{8, &Node{3, leaf(1), &Node{6, leaf(4), leaf(7)}}, &Node{10, nil, &Node{14, leaf(13), nil}}}
}

func main() {
	t := build()
	fmt.Println("E1. sum =", sum(t), ", maximum =", maxOf(t))
	fmt.Println("E2. nodes with one child:", oneChild(t))
	fmt.Println("E3. full?", isFull(t), ", is the subtree of 3 full?", isFull(t.Left))
	var l2 []int
	level(t, 2, &l2)
	fmt.Println("E4. level 2:", l2)
	fmt.Println("E5. root–leaf paths:")
	paths(t, "")
	fmt.Println("E6. same(t, copy) =", same(t, build()), ", same(t, t.Left) =", same(t, t.Left))
}