Tree

class Tree(object):
    class Position(object):
        def element(self):
            """ Trả về phần tử được lưu trữ tại vị trí """
            raise NotImplemented("must be Implemented by subclass")

        def __eq__(self, other):
            """return T if p stays at the same position"""
            raise NotImplemented("must be Implemented by subclass")

        def __ne__(self, other):
            return not (self == other)

        def root(self):
            raise NotImplemented("must be Implemented by subclass")

        def is_root(self, p):
            """"return True if p is root, otherwise return False"""
            return self.root()

        def is_leaf(self, p):
            return self.num_chilren(p) == 0

        def is_empty(self):
            return len(self) == 0

        def __len__(self):
            raise NotImplemented("must be Implemented by subclass")

        def parent(self, p):
            raise NotImplemented("must be Implemented by subclass")

        def chilren(self, p):
            raise NotImplemented("must be Implemented by subclass")

        def num_chilren(self):
            raise NotImplemented("must be Implemented by subclass")

        def depth(self, p):
            if self.is_root(p):
                return 0
            else:
                return 1 + self.depth(self.parent(p))

        def _height_recursive(self, p):

            if self.is_leaf:
                return 0
            else:
                return 1 + max(self._height_recursive(c) for c in self.chilren(p))

        def height(self, p = None):

            if p is None:
                p = self.root()
            return self._height_recursive(p)