import random

class Node :
    def __init__(self):
        self.v = None
        self.left = None
        self.right = None

class Tree :
    def __init__(self):
        self.root = None

def insert (t:Tree, v:int) :
    if t is None :
        return
    # creazione nuovo nodo
    nuovo = Node()
    nuovo.v = v
    # individuazione del nodo padre del nuovo nodo
    precedente = None
    i = t.root
    while i is not None :
        precedente = i
        if v>i.v :
            i = i.right
        else :
            i = i.left
    # inserisco il nodo nell'albero al punto
    # opportuno
    if precedente is None :
        # inserimento primo nodo (radice)
        t.root = nuovo
    else :
        if v>precedente.v :
            precedente.right = nuovo
        else :
            precedente.left = nuovo

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

def inOrderVisit (t:Tree) :
    inOrderVisitNode (t.root)

def inOrderVisitNode (u:Node) :
    # caso base : il nodo non esiste
    if u is None :
        return
    # caso ricorsivo
    inOrderVisitNode (u.left)
    print (u.v)
    inOrderVisitNode (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: ")
inOrderVisit (t)

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

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

#implementiamo la ricerca in modo ricorsivo

def searchRic (t:Tree, v:int) -> bool:
    return searchRicNode (t.root, v)

def searchRicNode (u:Node, v:int) -> bool:
    #casi base
    if u is None :
        return False
    if u.v == v :
        return True
    # caso ricorsivo
    if v>u.v :
        return searchRicNode (u.right, v)
    else :
        return searchRicNode (u.left, v)

print (searchRic(t, 20))
print (searchRic(t, 5))