"""
Nom : Implémentation objet d'un arbre binaire de recherche et d'un noeud
Développeur : Ander Arrosteguy
Date de mise à jour : 23/09/2019
"""

class BinarySearchTree:
    root = None
    size = 0
    internal_lc = 0
    external_lc = 0

    def __init__(self, root = None):
        if self.root != None:
            self.size += 1
        self.root = root

    #################################

    def setRoot(self, root = None):
        self.root = root

    def setSize(self, size):
        self.size = size

    def setInternalLc(self, internal_lc):
        self.internal_lc = internal_lc

    def setExternalLc(self, external_lc):
        self.external_lc = external_lc

    #################################

    def getRoot(self):
        return self.root

    def getHeight(self):
        return self.getRoot().getHeight()

    def getSize(self):
        return self.size

    def getInternalLc(self):
        return self.internal_lc

    def getExternalLc(self):
        return self.external_lc

    #################################

    def addNode(self, node, base = None):
        if not self.hasRoot():
            self.setRoot(node)
            return

        if base == None:
            base = self.getRoot()

        if node.getValue() <= base.getValue():
            if not base.hasLeftChild():
                base.addLeftChild(node)
                return
            else:
                self.addNode(node, base.getLeftChild())
        else:
            if not base.hasRightChild():
                base.addRightChild(node)
                return
            else:
                self.addNode(node, root.getRightChild())

        self.setSize(self.getSize() + 1)

    # Todo
    def removeNode(self, node):
        self.setSize(self.getSize() - 1)

    def hasRoot(self):
        return self.root != None

    def getLc(self):
        return self.getExternalLc() + self.internal_lc

    def getTreeHeight(self):
        return self.getRoot().getHeight()


class Node:
    value = 0
    parent = None
    leftChild = None
    rightChild = None

    def __init__(self, value, parent = None, leftChild = None, rightChild = None):
        self.value = value
        self.parent = parent
        self.leftChild = leftChild
        self.rightChild = rightChild

    #################################

    def setValue(self, value):
        self.value = value

    def setParent(self, parent = None):
        self.parent = parent

    def addLeftChild(self, leftChild):
        self.leftChild = leftChild

    def removeLeftChild(self):
        self.leftChild = None

    def addRightChild(self, rightChild):
        self.rightChild = rightChild

    def removeRightChild(self):
        self.rightChild = None

    #################################

    def getValue(self):
        return self.value

    def getParent(self):
        return self.parent

    def getLeftChild(self):
        return self.leftChild

    def getRightChild(self):
        return self.rightChild

    #################################

    def isRoot(self):
        return self.getParent() == None

    def isLeaf(self):
        return not self.hasChildren()

    def isBranch(self):
        return self.hasChildren()

    def hasLeftChild(self):
        return self.getLeftChild() != None

    def hasRightChild(self):
        return self.getRightChild() != None

    def hasChildren(self):
        return (self.getLeftChild() != None) or (self.getRightChild() != None)

    def getHeight(self):
        if not self.hasChildren():
            return 0

        heightLeft = 0
        heightRight = 0

        if self.hasLeftChild():
            heightLeft = self.getLeftChild().getHeight() + 1

        if self.hasRightChild():
            heightRight = self.getRightChild().getHeight() + 1

        if heightLeft > heightRight: return heightLeft
        else: return heightRight

    def factorBalance(self):
        return self.getRightChild().getHeight() - self.getLeftChild().getHeight()


if (__name__ == "__main__"):
    tree = BinarySearchTree()
    root = Node(5)

    tree.addNode(root)
    tree.addNode(Node(3))
    tree.addNode(Node(4))
    tree.addNode(Node(6))
    tree.addNode(Node(14))

    print(tree.getRoot().getRightChild().getRightChild().getValue())
    print(tree.getHeight())