from __future__ import annotations
from dataclasses import dataclass
import random

@dataclass
class Node :
    key:int
    #value: str
    left:Node|None = None
    right:Node|None = None

@dataclass
class Tree :
    root:Node|None = None

def insert (t:Tree, key:int) -> None:
    nuovo = Node (key)
    i:Node|None = t.root
    precedente:Node|None = None
    while i is not None :
        precedente = i
        if key > i.key:  
            i = i.right
        elif key < i.key:  
            i = i.left
        else: #non posso inserire chiavi duplicate
            return
    if precedente is None:
        # inserisco il primo node dell'albero
        t.root = nuovo
    else:
        if key > precedente.key:
            precedente.right = nuovo
        else:
            precedente.left = nuovo


def search (t:Tree, key:int) -> bool :
    i:Node|None = t.root
    while i is not None :
        if key > i.key:  
            i = i.right
        elif key < i.key:  
            i = i.left
        else: 
            return True
    return False


def in_order_visit (t:Tree):
    in_order_visit_node (t.root)
    
def in_order_visit_node (u:Node|None):
    # caso base
    if u is None:
        return
    # caso ricorsivo
    in_order_visit_node (u.left)
    print (u.key, end = " ")
    in_order_visit_node (u.right)
          
t1 = Tree()
insert (t1, 10)
insert (t1, 6)
insert (t1, 20)
insert (t1, 15)
insert (t1, 1)
in_order_visit (t1)
print()

def crea_random_tree (n:int, key_max:int) -> Tree :
    t = Tree()
    for _ in range (n):
        insert (t, random.randint(0, key_max))    
    return t

print ("t2:")
t2 = crea_random_tree (20, 10000)
in_order_visit (t2)


def search_ric (t:Tree, key:int) -> bool:
    return search_ric_node (t.root, key)

def search_ric_node (u:Node|None, key:int) -> bool:
    #caso base negativo
    if u is None :
        return False
    #caso base positivo
    if u.key == key :
               return True
    #caso ricorsivo
    if key > u.key:
        return search_ric_node (u.right, key)
    else:
        return search_ric_node (u.left, key)
    
# esercizio: calcolare in modo ricorsivo 
# l'altezza di un Tree, definita
# come 0 se l'albero è vuoto, 1 se c'è solo la radice
# e così via (ogni livello si incrementa di 1)