from __future__ import annotations
from dataclasses import dataclass
import random

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

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

def insert (t:Tree, v:int) :
    #creazione del nuovo nodo
    nuovo = Node (v)
    #troviamo la posizione per l'inserimento
    i:Node|None=t.root
    precedente:Node|None = None
    while i is not None:
        precedente = i
        if v > i.value:
            i = i.right
        else:
            i = i.left
    if precedente is None: 
        #sto inserendo il primo nodo (la radice)
        t.root = nuovo
    else:
        if v > precedente.value:
            precedente.right = nuovo
        else:
            precedente.left = nuovo

def search (t:Tree, v:int) -> bool :
    i = t.root
    while i is not None:
        if i.value==v:
            return True
        if v > i.value:
            i = i.right
        else:
            i = i.left
    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.value)
    in_order_visit_node(u.right)

t = Tree()
insert (t, 10)
insert (t, 20)
insert (t, 4)
insert (t, 100)
insert (t, 30)
print (search(t, 20))
print (search(t, 25))
print ("Visita in ordine: ")
in_order_visit (t)

print ("Elementi casuali: ")
for i in range (0,10) :
    v = random.randint(10, 200)
    print (v)
    insert (t, v)

print ("Visita in ordine: ")
in_order_visit (t)

#implementiamo la ricerca in modo ricorsivo

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

def search_ric_node (u:Node|None, v:int) -> bool:
    if u is None:
        return False
    if u.value==v :
        return True
    if v>u.value :
        return search_ric_node(u.right,v)
    else:
        return search_ric_node(u.left,v)
    

print (search_ric(t, 20))
print (search_ric(t, 5))