#from collections import deque

class ArbreBinaire:
    def __init__(self, L):
        if L:
            self.root = L[0]
            self.filsGauche = ArbreBinaire(L[1])
            self.filsDroit = ArbreBinaire(L[2])          
        else:
            self.root = None
            self.filsGauche = None
            self.filsDroit = None

    def arbor(self, space = 0):
        if self.root != None:
            print(" "*space,self.root)
            if self.filsGauche.root == None:
                spaces = " " * (space + 2)
                print(spaces,"-")
            else:
                self.filsGauche.arbor(space + 2)
            if self.filsDroit.root == None:
                spaces = " " * (space + 2)
                print(spaces,"-")
            else:
                self.filsDroit.arbor(space + 2)

    def infixe(self, L = []):
        if self.filsGauche:
            self.filsGauche.infixe(L)
        if self.root != None:
            L.append(self.root)
        if self.filsDroit:
            self.filsDroit.infixe(L)
        return L

    def isABR(self):
        L = self.infixe()
        prev = None
        for node in L:
            if prev is None:
                prev = node
            elif node < prev:
                return False
        return True

    def min_max(self):
        L = self.infixe()      
        return L[0], L[-1]

    def hauteur(self):
        # Initialiser les hauteurs des sous-arbres à -2 si les sous-arbres n'existent pas
        hauteur_gauche = -2
        hauteur_droite = -2

        # Vérifier si le sous-arbre gauche existe et mettre à jour sa hauteur
        if self.filsGauche is not None:
            hauteur_gauche = self.filsGauche.hauteur()

        # Vérifier si le sous-arbre droit existe et mettre à jour sa hauteur
        if self.filsDroit is not None:
            hauteur_droite = self.filsDroit.hauteur()

        # Retourner la hauteur maximale entre les deux sous-arbres, plus 1
        return 1 + max(hauteur_gauche, hauteur_droite)

    def isAVL(self):
        if self.filsDroit is not None:
            hD =  self.filsDroit.hauteur()
        else:
            hD = 0
            
        if self.filsGauche is not None:
            hG = self.filsGauche.hauteur()
        else:
            hG = 0
            
        if abs(hD-hG) > 1:
            return False
        
        if self.filsDroit is not None:
            d = self.filsDroit.isAVL()
            if not d:
                return d
            
        if self.filsGauche is not None:
            g = self.filsGauche.isAVL()
            if not g:
                return g
            
        return True

        
L = [ 
    10, 
        [ 7, 
            [5, 
                [], 
                [] 
            ], 
            [9, 
                [8, 
                    [45,
                        [56, 
                            [ ],
                            []
                        ],
                        []
                    ], 
                    [55, 
                        [],
                        []
                    ] 
                ], 
                [10, 
                    [], 
                    [] 
                ] 
            ] 
        ], 
        [ 15, 
            [ ], 
            [ 18, 
                [17, [], []], 
                [ ] ] 
        ] 
    ]
    

A = ArbreBinaire([ 10, [ 7, [5, [], [] ], [9, [8, [], [] ], [10, [], [] ] ] ], [ 15, [ ], [ 18, [17, [], []], [ ] ] ] ])
#A = ArbreBinaire(L)

A.arbor()
print(A.isAVL())