binary_search_tree.py

import math
from collections import deque


class Node:
    """ 
    A node of the binary search tree

    Attributes
    __________
    key: int
        Stored key to the data
    data: any
        Stored data
    left: Node
        Left child node
    right: Node
        Right child node 
    """
    def __init__(self, data, key):
        """
        Parameters
        __________
        key: int
            Stored key to the data
        data: any
            Stored data
        """
        self.left = None # left child
        self.right = None # right child
        self.parent = None # parent node
        
        self.key = key 
        self.data = data

class BinarySearchTree:
    """
    Binary Search Tree (BST)

    Attributes
    __________

    root: Node
        The root node of the BST
    """
    def __init__(self):
        self.root = None

    def insert(self, node, parent=None):
        """ 
        Insertion of the new nodes 
        
        Parameters
        __________

        node: Node
            The node that should be inserted
        root: Node, optional
            The node that is considered at the certain moment (by default it is root node)
        """
        
        # If empty BST
        if not self.root:
            self.root = node
            return
        
        # Starting point is root
        if not parent:
            parent = self.root

        # Less -> left 
        # Large or equal -> right

        if node.key < parent.key:
            if parent.left:
                self.insert(node, parent=parent.left) # call recursively
            else:
                parent.left = node # add new node
                parent.left.parent = parent # define parent node for new node 
        else:
            if parent.right:
                self.insert(node, parent=parent.right) # call recursively
            else:
                parent.right = node # add new node
                parent.right.parent = parent # define parent node for new node
    
    def search(self, key, root=None):
        """ 
        Searching of the data by keys 

        Parameters
        __________

        key: int
            Key for the searching
        root: Node, optional
            The node that is considered 
            at the certain moment (by default it is root node)
        """

        # If empty BST
        if not self.root:
            print("Empty BST!")
            return

        # Starting point is root 
        if not root:
            root = self.root
        
        # Less -> left 
        #Large or equal -> right

        if root.key == key:
            return root.data
        elif key < root.key :
            if root.left:
                return self.search(key, root=root.left) # call recursively
            else:
                print(f"No data for this key ({key})!")
        else:
            if root.right:
                return self.search(key , root=root.right) # call recursively
            else:
                print(f"No data for this key ({key})!")

    def direct_traversal(self, 
                        root=None, 
                        output_list=None):
        """ 
        In-depth direct traversal (pre-order)
        
        Parameters
        __________

        root: Node, optional
            Considered node (root at the start)
        output_list: list, optional
            Output list (result of traversal)
        """
        if not output_list:
            output_list = []
        if not root:
            root = self.root
        output_list.append(root.key)
        
        if root.left:
            self.direct_traversal(root=root.left,
                                  output_list=output_list)
        
        if root.right:
            self.direct_traversal(root=root.right,      
                                  output_list=output_list)

        return output_list
    
    
    def get_height(self):
        """ Height of the binary tree is log2(N) """
        return math.ceil(math.log2(self.get_length()))

    def get_length(self):
        """ Number of elements N """
        return len(self.in_order_traversal())

    def __breadth_first_traversal(self, current_node, output_list, level):
        
        if not current_node:
            return
        
        if level == 0:
            output_list.append(current_node.key)
        
        elif level > 1:
            self.__breadth_first_traversal(current_node.left, level+1)
            self.__breadth_first_traversal(current_node.right, level-1)
        
    def breadth_first_traversal(self):
        """ 
        Breadth-first traversal. 
        Queues based approach.
        
        """
        queue = deque()
        queue.append(self.root)
        output_list = [self.root.key]
        while len(queue):
            current_node = queue.popleft()
            if current_node.left:
                output_list.append(current_node.left.key)
                queue.append(current_node.left)
            if current_node.right:
                output_list.append(current_node.right.key)
                queue.append(current_node.right)
        return output_list
        
    def __in_order_traversal(self, current_node, output_list):
        """ 
        In-depth in-order traversal. 
        Returns sorted list of arrays (ascending).
         
        
        Parameters
        __________

        current_node: Node
            Considered node (root at the start)
        output_list: list
            Output list (result of traversal)
        """
        # check leaves (recursion break)
        if not current_node:
            return
        
        # Find the "most left"
        self.__in_order_traversal(current_node.left, output_list)
        
        # Node visiting
        output_list.append(current_node.key)
        
        # Find the "most right"
        self.__in_order_traversal(current_node.right, output_list)
        
        # Return result of visitings
        return output_list


    def in_order_traversal(self):
        """ 
        In-depth in-order traversal (callable)
        """
        return self.__in_order_traversal(self.root, [])
        
    def __post_order_traversal(self, current_node, output_list):
        """ 
        In-depth post-order traversal 
        
        Parameters
        __________

        current_node: Node
            Considered node (root at the start)
        output_list: list
            Output list (result of traversal)
        """
        # check leaves (recursion break)
        if not current_node:
            return
        
        # Find the "most left"
        self.__post_order_traversal(current_node.left, output_list)
        # Find the "most right"
        self.__post_order_traversal(current_node.right, output_list)
        
        # Node visiting
        output_list.append(current_node.key)

        # Return result of visitings
        return output_list 
    
    def post_order_traversal(self):
        """ 
        In-depth post-order traversal (callable)
        """
        return self.__post_order_traversal(self.root, [])    


# Initialization    
bst = BinarySearchTree()

bst.insert(Node(key=4, data='Four'))

# Insert root
print(bst.root.data)

# Insert right and left nodes
bst.insert(Node(key=5, data='Five'))
bst.insert(Node(key=2, data="Two"))
bst.insert(Node(key=3, data="Three"))


# Check
print(f"Left child of root: {bst.root.left.key}")
print(f"Left child of root: {bst.root.right.key}")

# Insert another one
bst.insert(Node(key=1, data="One"))

# Search by keys
for i in (5, 7):
    res = bst.search(i)
    if res:
        print(f"Serched data for key {i}: {res}")


# Traversals
print("Pre-order: ", bst.direct_traversal())
print("In-order: ",bst.in_order_traversal())
print("Post-order: ",bst.post_order_traversal())
print("Breadth-first: ", bst.breadth_first_traversal())

# Height
print(bst.get_height())

linked_list.py

# python 3.8

class Node:
    """
    Attributes
    __________
    data: any
        Stored data
    next: Node
        Link to the next node
    """
    def __init__(self, data=None):
        """         
        Parameters
        ----------
        data: any, optional
            Stored data
        """
        self.data = data
        self.next = None

class LinkedList:
    """
    Attributes
    __________
    head: Node
        The first node of the linked list
    len: int
        The length of the linked list
    """

    def __init__(self, head=None):
        """         
        Parameters
        ----------
        head: Node, optional
            The first node of the linked list
        """
        if head:
            # Type checking 
            if isinstance(head, Node):
               self.head = head # initialized linked list
               self.len = 1 
            else:
                print("Wrong type for the node")
        else:
            self.len = 0 # empty linked list
    
    # Adding 
    
    def __add_to_beggin(self, new_node):
        """ 
        Adds to the beggining 
        
        Parameters
        ----------
        new_node: Node
            New node which should be added
        """
        if self.len == 0:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.len = self.len + 1


    def __add_to_end(self, new_node):
        """ Add to the end 
        
        Parameters
        ----------
        new_node: Node
            New node which should be added
        """
        if self.len == 0:
            self.__add_to_beggin(new_node)
        else:
            node = self.head
            while True:
                if node.next:
                    node = node.next
                else:
                    break
            node.next = new_node
            self.len = self.len + 1
    
    def __add_to_midddle(self, 
                         new_node, 
                         possition_index):
        """
        Adds to the N-th possition 
        
        Parameters
        ----------
        new_node: Node
            New node which should be added
        possition_index: int
            The possition index where new node should be inserted
        """

        node = self.head
        previous = None
        for _ in range(possition_index):
            previous = node
            node = previous.next
        
        previous.next = new_node
        new_node.next = node

        self.len = self.len + 1
    
    # Removing

    def __remove_from_begin(self):
        """ Removes from the beggining """
        if self.len > 0:
            self.head = self.head.next
            self.len = self.len - 1

    def __remove_from_end(self):
        """ Removes from the end """
        
        node = self.head
        previous = None
        while True:
            if node.next:
                previous = node
                node = previous.next
            else:
                break
        previous.next = None
        self.len = self.len - 1

    def __remove_from_middle(self, possition_index):
        
        """ Removes from the N-th position 
        
        Parameters
        ----------
        possition_index: int
            The possition index where node should be removed
        """   

        node = self.head
        previous = None
        for _ in range(possition_index):
            previous = node
            node = previous.next
        previous.next = node.next
        self.len = self.len - 1

    # Callable methods

    def insert(self, 
               new_node, 
               possition_index=None):
        
        """ Inserts new nodes 
        
        Parameters
        ----------
        new_node: Node
            New node which should be added
        possition_index: int, optional
            The possition index where new node should be inserted
        """    
        
        if possition_index is None: 
            if self.len == 0:
                self.__add_to_beggin(new_node)
            else:
                self.__add_to_end(new_node)
        elif possition_index == 0:
            self.__add_to_beggin(new_node)
        elif possition_index > self.len:
            print("Linked link is shorter than you expect")
        else:
            self.__add_to_midddle(new_node, possition_index)

    def remove(self, possition_index=None):
        """ Removes nodes 
        
        Parameters
        ----------
        possition_index: int, optional
            The possition index where node should be removed
        """
        if self.len > 0:    
            if possition_index is None:
                if self.len > 0:
                    self.__remove_from_end()
            elif possition_index == 0:
                self.__remove_from_begin()                
            elif possition_index > self.len:
                print("Linked link is shorter than you expect")
            else:
                self.__remove_from_middle(possition_index)
        else:
            print("This is already empty list")


def print_all_elements(linked_list):
    """ 
    Prints all elements of the linked list 
    
    Parameters
    ----------
    linked_list: LinkedList
        Linked list which should be printed
    """
    if linked_list.head:
        node = linked_list.head
        elements = []
        while True:
            elements.append(str(node.data))
            if node.next and node.next.data:
                node = node.next
            else:
                break
        elements = f" ".join(elements)
        print(f"Linked list elements:\n {elements}")
    else:
        print("Empty linked list")

#Wrong type
wrong_case = LinkedList(1)

# Initialize linked list
ll = LinkedList()
ll.insert(Node(1))
print(f"Head: {ll.head.data}")

#Add to the begining

print("\nAdd to the begining")
ll.insert(Node(0), 0)
print(f"Head: {ll.head.data}")
print_all_elements(ll)

# Add to the end

print("\nAdd to the end")
ll.insert(Node(3))
print(f"Head: {ll.head.data}")
print_all_elements(ll)

# Add to the N

print("\nAdd to the index 2")
ll.insert(Node(2), 2)
print(f"Head: {ll.head.data}")
print_all_elements(ll)

# Remove from the N
print("\nRemove from the index 2")
ll.remove(2)
print(f"Head: {ll.head.data}")
print_all_elements(ll)

# Remove from the end
print("\nRemove from the end")
ll.remove()
print(f"Head: {ll.head.data}")
print_all_elements(ll)

# Remove from the begging
print("\nRemove from begging")
ll.remove(0)
print(f"Head: {ll.head.data}")
print_all_elements(ll)

# Try to remove to large index
print("\nTry to remove to large index (100)")
ll.remove(100)


# Make empty
print("\nRemove from begging")
ll.remove(0)
print_all_elements(ll)

# Try remove more
print("\nRemove from empty")
ll.remove()