import sys

class Noeud:
    def __init__(self, v, c = []):
        self.v = v
        self.c = c

def parcours_affiche(arbre):
    for c in arbre.c:
        parcours_affiche(c)

    print(arbre.v)


def parcours_recherche(arbre, valeur):

    if arbre is None:
        return False

    stack = arbre.c

    if valeur > arbre.v:
        return False

    if valeur == arbre.v:
        return True

    prev = sys.maxsize

    while len(stack) > 0:
        children = stack.pop(0)
        if valeur == children.v:
            return True
        if valeur > prev and valeur < children.v:
            stack = children.c
            prev = stack[0].v
        else:
            prev = children.v

    return False    

if __name__=="__main__": 

    racine = Noeud(13, [Noeud(4, [Noeud(1), Noeud(2), Noeud(3)]), Noeud(8, \
    [Noeud(5), Noeud(6), Noeud(7)]),  Noeud(12, [Noeud(9), Noeud(10), Noeud(11)])])

    print(parcours_affiche(racine))

    # renvoie False pour un arbre vide
    parcours_recherche(None, -1)

    # 11 est dans l'arbre
    assert parcours_recherche(racine, 11) == True

    # 12 n'est pas dans l'arbre
    assert parcours_recherche(racine, 12) == False