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):
        return 1 + max(
            self.left.hauteur() if self.left else -1,
            self.right.hauteur() if self.right else -1
        )

    def trouve(self , data):
        if data == self.data:
            return self
        elif data < self.data and self.left != None:
                return self.left.trouve(data)
        elif data > self.data and self.right != None:
            return self.right.trouve(data)
        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:
            node = node.left
        return node

    def successeur(self):
        if self.right:
            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 == None and self.right == 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 == None:
                if self.parent.left != None and self.parent.left.data == data:
                   self.parent.left = self.right
                else:
                    self.parent.right = self.right
                del self
            elif self.right == None:
                if self.parent.left != 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():
                    succ.parent.left = succ.right
                else:
                    succ.parent.right = succ.right
                if succ.right:
                    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())