class Node:
    def __init__(self, val): #defining class node and initializing values
        self.l = None #left
        self.r = None #left
        self.v = val #value

class Tree: #new class tree
    def __init__(self):
        self.root = None #root
        self.size = 0 #size

    def getRoot(self):
        return self.root #return root

    def add(self, val): #public add
        self.size+=1
        if(self.root == None): #if the root is none
            self.root = Node(val) #the root =the new value
        else:
            self._add(val, self.root) #if not, then we use the add method below

    def _add(self, val, node): #non public add
        if(val < node.v): #if less than node
            if(node.l != None): #if not empty
                self._add(val, node.l) #redo function on that node
            else:
                node.l = Node(val) #add to left if node is empty
        else:
            if(node.r != None): #same for right side if greater than
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val): #search and return
        if(self.root != None): #if root isn't empty
            return self._find(val, self.root) #return the value from our nonpublic find method
        else:
            return None #if empty return none

    def _find(self, val, node):
        if(val == node.v): #check current node
            return node
        elif(val < node.v and node.l != None): #if less than current move to left
            self._find(val, node.l)#recurse
        elif(val > node.v and node.r != None): #if greater than, move to right
            self._find(val, node.r) #recursively run

def avg_cmp(bst): #average comparisons (basically computing mean)
    return _sum_cmp(bst.root,0)/bst.size #using sum method on bst divided by size

def _sum_cmp(root,depth):

    if root == None:
        return 0 #0 for empty tree

    return _sum_cmp(root.l,depth+1)+_sum_cmp(root.r,depth+1)+depth+1 #summing

def max_depth(bst): #max depth
    return max_height(bst)

def max_height(bst): #max height
    return _max_height(bst.root,0)

def _max_height(root,depth):

    if root == None: #if none
        return depth-1 #return depth - 1

    return max(_max_height(root.l,depth+1),_max_height(root.r,depth+1)) #recurse

def avg_height(bst):
    return -(avg_cmp(bst)-(max_height(bst)+1)) #- (avg comparison - max height +1)

def avg_depth(bst):
    return avg_cmp(bst)-1 #avg comparisons - 1

def _sum_height(root,depth,maxHeight):

    if root == None:
        return 0 # 0 if no root

    return _sum_height(root.l,depth+1,maxHeight)+_sum_height(root.r,depth+1,maxHeight)+(maxHeight-depth) recurse