from collections import deque

class ABR:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None

    def insert(self, data):
        if data <= self.data:
            if self.left == None:
                self.left = ABR(data)
                self.left.parent = self
            else:
                self.left.insert(data)
        else:
            if self.right == None:
                self.right = ABR(data)
                self.right.parent = self
            else:
                self.right.insert(data)

    def affiche(self, h = 0):
        if self.right:
            self.right.affiche(h + 1)
        spaces = ' ' * 7 * h
        print(spaces,self.data)
        if self.left:
            self.left.affiche(h + 1)

    def hauteur(self):
        hauteur_gauche = -1
        hauteur_droite = -1

        if self.left is not None:
            hauteur_gauche = self.left.hauteur()

        if self.right is not None:
            hauteur_droite = self.right.hauteur()

        return 1 + max(hauteur_gauche, hauteur_droite)

    def trouve(self, data):
        # Si la donnée correspond à la donnée courante
        if data == self.data:
            return self

        # Si la donnée est inférieure à la donnée courante et qu'il y a un sous-arbre gauche
        if data < self.data and self.left is not None:
            return self.left.trouve(data)

        # Si la donnée est supérieure à la donnée courante et qu'il y a un sous-arbre droit
        if data > self.data and self.right is not None:
            return self.right.trouve(data)

        # Si la donnée n'est pas trouvée
        return None


    def liste(self, L = []):
        L.append(self.data)
        if self.left != None:
            self.left.liste(L)
        if self.right != None:
            self.right.liste(L)
        return sorted(L)

    # l'enfant est-il le fils gauche de son parent ?
    def is_left_child(self):
        return self.parent and self is self.parent.left

    # l'enfant est-il le fils droit de son parent ?
    def is_right_child(self):
        return self.parent and self is self.parent.right

    def minimum(self):
        node = self
        while node.left is note None:
            node = node.left
        return node

    def successeur(self):
        if self.right is not None:
            return self.right.minimum()
        node = self
        while node.is_right_child():
            node = node.parent
        return node.parent

    def delete(self, data):
        if not self.trouve(data):
            return

        if data == self.data:
            # si le noeud n'a pas de fils
            if self.left is None and self.right is None:
                if self.parent.left.data == data:
                    self.parent.left = None
                else:
                    self.parent.right = None
                del self
            # si le noeud a un fils, on le remplace par son fils
            elif self.left is None:
                if self.parent.left is not None and self.parent.left.data == data:
                   self.parent.left = self.right
                else:
                    self.parent.right = self.right
                del self
            elif self.right is None:
                if self.parent.left is not None and self.parent.left.data == data:
                   self.parent.left = self.left
                else:
                    self.parent.right = self.left
                del self
            else:
                succ = self.successeur()
                self.data = succ.data
                if succ.is_left_child() is not None:
                    succ.parent.left = succ.right
                else:
                    succ.parent.right = succ.right
                if succ.right is not None:
                    succ.right.parent = succ.parent
                del succ
            
        elif data < self.data:
            self.left.delete(data)
        else:
            self.right.delete(data)


A = ABR(150)
for v in [45,12,200,175,18,17,7,10,3,31,250,180,100]:
    A.insert(v)
print(A.hauteur())