Implementation of Linked Binary Tree DS

LinkedBinaryTree.py

# Implementing Linked Binary Tree 
#     ____________
#    |L |PARENT|R_|
#    |L_|_DATA_|R_|  

from tree import BinaryTree

class LinkedBinaryTree(BinaryTree):

    class _Node:
        """ Creating a Tree Node """
        __slots__ = '_element', '_parent', '_left', '_right'
        def __init__(self, element, parent=None, left=None, right=None):
            self._element = element
            self._parent  = parent
            self._left = left
            self._right = right

    class Position(BinaryTree.Position):

        def __init__(self, container, node):
            self._container = container
            self._node = node

        def element(self):
            return self.node._element

        def __eq__(self):
            return container == self

        def __ne__(self):
            return not(container == self)

    def _validate(self, p):
        """ Validate if given position is True """
        if not isinstance(p, self.Position):
            raise TypeError(' Must be of same type ')
        if p._container is not self:
            raise ValueError(' P Not belong to same position ')
        if p._node._parent is p._node:
            raise ValueError(' P is no longer valid ')
        return p

    def _make_position(self, node):
        return self.Position(self, node) if node is not None else None

    
    def __init__(self):
        self._root = None   # Root node of Tree
        self._size = 0

    def __len__(self):
        return self._size
    
    ### PUBLIC ACCESSORS ###
    def root(self):
        return self._make_position(self._root)

    def is_root(self, node):
        return node is self._root

    def parent(self, node):
        node = self._validate(node)
        return self._make_position(node._parent)

    def left_child(self, node):
        node = self._validate(node)
        return self._make_position(node._left)

    def right_child(self, node):
        node = self._validate(node)
        return self._make_position(node._right)

    def number_children(self, node):
        """ node represent Parent here """
        node = self._validate(node)
        count = 0
        if node._left is not None:
            count += 1
        if node._right is not None:
            count += 1
        return count

    def _add_root(self, node):
        if self._root is not None:
            raise ValueError(' Root Exists ')
        self._size += 1
        self._root = self._Node(node)
        return self._make_position(self._root)

    def _add_left(self, parent, data):
        """ Adding a node to the left of a Tree """
        parent = self._validate(parent)     # Check if parent's position is valid
        if parent._left is not None:
            raise ValueError(' left children Exists ')
        parent._left = self._Node(node, parent)
        self._size += 1
        return self._make_position(parent._left)

    def _add_right(self, parent, data):
        """ Adding a node to the right of a Tree """
        parent = self._validate(parent)
        if parent._right is not None:
            raise ValueError(' Right Children Exists ')
        parent._right = self._Node(node)
        self._size += 1
        return self._make_position(parent._right)

    def _replace(self, parent, data):
        """ Replacing P's element with e """
        parent = self._validate(parent)
        old = parent._element
        parent._element = data
        return old

    def _delete(self, node):
        """ Deleting the given node """
        node  = self._validate(node)
        if self.number_children(node) == 2:
            raise ValueError(' It\'s a Perfect Binary Tree ')
        child = node.left if node.left else node.right
        if child is not None:
            child._parent = node._parent
        if node is self.root:
            self.root = child
        else:
            parent = node._parent
            if node is parent.right:
                parent.right = child
            parent.left = child

        self._size += 1
        node._parent = node
        return node._element

tree.py

# Creating Abstract base class -> Tree


class Tree:
    """ Abstract base class for tree data structure. 
    argument node in class methods represent Position of a node """

    class Position:
        """ Representing the location of single element """

        def element(self):
            raise NotImplemented("must be implemented by sub clas")

        def __eq__(self, pos):
            # return self == pos     True if the pos. representing the same location
            raise NotImplemented("must be implemented by sub clas")

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

    def root(self):
        """ position root node of a tree """
        raise NotImplemented("must be implemented by sub clas")

    def is_root(self, node):
        """ if node is root of a tree or not """
        self.root() == node

    def parent(self, node):
        """ position of node's parent """
        raise NotImplemented("must be implemented by sub clas")

    def num_children(self, node):
        """ no. of children node have """
        raise NotImplemented("must be implemented by sub clas")

    def children(self, node):
        """ generate iteration of node's children """
        raise NotImplemented("must be implemented by sub clas")

    def is_leaf(self, node):
        """ if node doesn't have any children """
        raise NotImplemented("must be implemented by sub clas")

    def __len__(self, t):
        """ compute length(total no. of elements) of tree """
        raise NotImplemented("must be implemented by sub clas")

    def is_empty(self):
        return self.__len__() == 0

    def position(self):
        pass

    def iter(self):
        pass


## Defining Binary Tree ADT

class BinaryTree(Tree):

    def left(self, node):
        """ Position of node's left child """
        raise NotImplementedError("must be implemented by subclass")

    def right(self, node):
        """ Position of node's right child """
        raise NotImplementedError("must be implemented by subclass")

    def sibling_try(self, node):
        """ Positions of node's siblings """
        parent = node.Parent()
        for i in self.childrens(parent):
            if i != node:
                print(i)
    
    def sibling(self, node):
        """ Position of node's sibling """
        parent = self.parent(node)
        if parent is None:
            return None
        else:
            if parent == self.left(parent):
                return self.right(parent)
            return self.left(parent)

    def children(self, node):
        """ Return left and right children of node"""
        if self.left(node) is not None:
            return self.left(node)
        if self.right(node) is not None:
            return self.right(node)