#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 == 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):
        return  1+max(
            self.filsGauche.hauteur() if self.filsGauche else -2,
            self.filsDroit.hauteur() if self.filsDroit else -2
        )

    def isAVL(self):
        hD =  self.filsDroit.hauteur() if self.filsDroit != None else 0
        hG =  self.filsGauche.hauteur() if self.filsGauche != None else 0

        if abs(hD-hG) > 1:
            return False
        
        if self.filsDroit != None:
            d = self.filsDroit.isAVL()
            if not d: return d
        if self.filsGauche != 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())