f

package main

import "fmt"
import "math"


type Node[T any] struct {
    value T
    left, right *Node[T]
}

func NewNode[T any](value T) *Node[T] {
    return &Node[T]{value: value}
}

type Queue[T any] struct {
    values []T
}

func NewQueue[T any]() *Queue[T] {
    return &Queue[T]{values: make([]T, 0)}
}

func (q* Queue[T]) IsEmpty() bool {
    return len(q.values) == 0
}

func (q* Queue[T]) Size() int {
    return len(q.values)
}

func (q* Queue[T]) Enqueue(value T) {
    q.values = append(q.values, value)
}

func (q* Queue[T]) Dequeue() T {
    if q.IsEmpty() {
        var zero T
        return zero
    }
    value := q.values[0]
    q.values = q.values[1:]
    return value
}

func print_tree[T any](n *Node[T]) {
    if n == nil {
        return
    }
    q := NewQueue[*Node[T]]()
    q.Enqueue(n)
    for !q.IsEmpty() {
        size := q.Size()
        for size > 0 {
            currNode := q.Dequeue()
            fmt.Printf("%v, ", currNode.value)
            if currNode.left != nil {
                q.Enqueue(currNode.left)    
            }
            if currNode.right != nil {
                q.Enqueue(currNode.right)    
            }
            size--
        }
        fmt.Println("")
    }
}

func build_tree[T any](values ...T) *Node[T] {
    if len(values) == 0 {
        return nil
    }
    middle := len(values)/2
    n := NewNode[T](values[middle])
    n.left = build_tree[T](values[:middle]...)
    n.right = build_tree[T](values[middle+1:]...)
    return n
}


func is_tree_balanced[T any](root *Node[T]) bool {
    return get_height(root) > -1
}

func get_height[T any](root *Node[T]) int {
    if root == nil {
        return 0
    }
    leftH := get_height(root.left)
    if leftH == -1 {
        return leftH
    }
    rightH := get_height(root.right)
    if rightH == -1 {
        return rightH
    }
    diff := rightH - leftH
    if diff > 1 || diff < -1 {
        return -1
    }
    return int(math.Max(float64(leftH), float64(rightH))) + 1
    
}

func main() {
    tree := build_tree(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
    fmt.Printf("%v\n", is_tree_balanced(tree))
}