class Noeud:
    def __init__(self,valeur,gauche=None,droit=None,parent=None):
        self.cle = valeur
        self.gauche = gauche
        self.droit = droit
        self.parent=parent
        
     
        
class Arbre:
    def __init__(self,racine=None):
        #initialise une instance d'arbre vide
        self.racine = racine
        
    def cle(self):
        #Renvoie la clé de la racine de l'instance d'arbre
        return self.racine.cle
    def sad(self):
        #renvoie le sous arbre droir de l'instance
        return Arbre(self.racine.droit)
    def sag(self):
        #renvoie le sous arbre gauche de l'instance
        return Arbre(self.racine.gauche)
    def est_vide(self):
        #renvoie True si l'instance d'arbre est vide
        #False sinon
        return self.racine is None
    
    def parcours_infixe(self):
        if  self.est_vide():
            return
        else:
            self.sag().parcours_infixe()
            #on affiche le noeud
            print(self.racine.cle , end =' ')
            self.sad().parcours_infixe()

    def arbre_rechercher(self,val):
        r=self.racine
        if self.racine==None:
            return False
        elif r.cle == val:
            return True
        elif val < r.cle:
            return self.sag().arbre_rechercher(val)
        else:
            return self.sad().arbre_rechercher(val)
    def max_arb(self):
        '''
        on suppose arbre non vide
        '''
        if self.sad().est_vide():
            return self.racine
        return self.sad().max_arb()  
        
    def min_arb(self):
        '''
        on suppose arbre non vide
        '''
        if self.sag().est_vide():
            return self.racine
        return self.sag().min_arb() 
    
    def arb_successeur(self,x):
        
        if x.droit!=None:
            return Arbre(r.droit).min_arb().cle
        y=x.parent
        while y!=None and y.droit==x:
            x=y
            y=y.parent
        if y==None:
            print("ce noeud n'a pas de successeur")
            return 
        return y.cle