class Stack(object):
    def __init__(self):
        self.items = []

    def __len__(self): # It returns the number of elements in the stack.
        return len(self.items)

    def push(self, item): # It adds a new item to the top of the stack. 
        self.items.append(item)

    def pop(self): # It removes the top element from the stack and returns the removed item.
        if not self.is_empty():
            return self.items.pop() # The Python's pop() method takes a single argument (index). If an argument is not passed to the function, it uses the default index -1. 

    def peek(self): # It returns the top element from the stack but does not remove it.
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self): # It returns true when the stack is empty, otherwise, the method returns false. 
        return len(self.items) == 0

    def __str__(self): # It allows us to print our stack.
        s = "{ "
        for i in range(len(self.items)):
            if i != len(self.items)-1:
                s += str(self.items[i]) + ", "
            else:
                s += str(self.items[i]) + " }"

        return s

    @classmethod
    def createRandomStack(cls, n):
        myStack = Stack()
        for i in range(n):
            i = random.randint(0, 100)
            myStack.push(i)

        return myStack
def main():
    myStack = Stack.createRandomStack(10)
    print(myStack) # { 58, 8, 91, 52, 98, 30, 41, 4, 32, 37 }
    print(len(myStack)) # 10
    print(myStack.pop()) # 37
    print(myStack) # { 58, 8, 91, 52, 98, 30, 41, 4, 32 }

if __name__ == '__main__':
    main()

class Queue():
    def __init__(self):
        self.items = []

    def __len__(self): # It returns the number of elements in the queue.
        return len(self.items)

    def enqueue(self, item): # It adds a new item to the tail of the queue. _The tail of the queue is the first element in our list.
        self.items.insert(0, item)

    def dequeue(self): # It removes the first element from the queue (the element at the head of the queue) and returns the removed item.
        if not self.is_empty():
            return self.items.pop()

    def is_empty(self): # It returns true when the queue is empty, otherwise, the method returns false. 
        return len(self.items) == 0

    def peek(self): # It returns the first element from the queue but does not remove it.
        if not self.is_empty():
            return self.items[-1]

    def __str__(self):  # It allows us to print our queue.
        s = "{ "
        for i in range(len(self.items)):
            if i != len(self.items)-1:
                s += str(self.items[i]) + ", "
            else:
                s += str(self.items[i]) + " }"

        return s

    @classmethod
    def createRandomQueue(cls, n):
        myQueue = Queue()
        for i in range(n):
            i = random.randint(0, 100)
            myQueue.enqueue(i)

        return myQueue

def main():
    myQueue = Queue.createRandomQueue(10)
    print(myQueue) # { 76, 2, 15, 58, 60, 1, 30, 77, 35, 7 }
    print(len(myQueue)) # 10
    print(myQueue.dequeue()) # 7
    print(myQueue) # { 76, 2, 15, 58, 60, 1, 30, 77, 35 }

if __name__ == '__main__':
    main()

import doctest
import heapq
import random
from heapq import heappush, heappop
from copy import deepcopy

class PriorityQueue:
    """ It implements a priority queue. 
    A priority queue sorts and dequeues elements based on their priorities.

    Args:
        heap : It uses the heap data structure provided by heapq to create a priority queue.
        The smallest element will be popped out the first from the queue regardless of the order in which the elements were queued.
    """     
    def __init__(self):
        self.heap = []
 
    def push(self, e):
        """
        It inserts a new element 'e'.
        >>> myQueue = PriorityQueue.createFromList([12, 9, 3, 14, 29, 4, 5, 13, 18])
        >>> myQueue.push(7)
        >>> print(myQueue)
        { 3 4 5 7 9 12 13 14 18 29 }
        """
        heappush(self.heap, e) # heappush insert the element e into the heap, _but the order is adjusted to maintain the heap properties_.
 
    def pop(self):
        """
        It removes the minimum element from the queue.
        >>> PriorityQueue.createFromList([12, 9, 3, 14, 9, 4, 5, 13, 18]).pop()
        3
        """
        return heappop(self.heap) # heappop removes the smallest element from the heap, _but the order is adjusted to maintain the heap properties_.

    def is_empty(self):
        """
        It returns true when the queue is empty; otherwise, the method returns false. 
        >>> PriorityQueue.createFromList([12, 9, 3, 14, 9, 4, 5, 13, 18]).is_empty()
        False
        >>> PriorityQueue.createFromList([]).is_empty()
        True
        """
        return len(self.heap)==0

    def __len__(self): 
        """
        It returns the number of elements in the priority queue.
        >>> len(PriorityQueue.createFromList([12, 9, 3, 14, 29, 4, 5, 13, 18]))
        9
        """
        return len(self.heap)

    def __str__(self): 
        """
        It allows us to print out our priority queue.
        >>> print(PriorityQueue.createFromList([12, 9, 3, 14, 29, 4, 5, 13, 18]))
        { 3 4 5 9 12 13 14 18 29 }
        """
        copy = deepcopy(self)
        s = "{"
        while not copy.is_empty():
            s += " " + str(copy.pop())

        s += " }"
        return s
    
    @classmethod
    def createFromList(cls, myList):
        """
        It takes as input a list and transforms it into a priority queue.
        """
        myPriorityQueue = PriorityQueue()
        heapq.heapify(myList) # heapify converts the list into a heap data structure.
        myPriorityQueue.heap = myList
        return myPriorityQueue

    @classmethod
    def createRandomPriorityQueue(cls, n):
        """
        It creates a priority queue with n random numbers.
        """
        myList = [random.randint(1, 20) for i in range(n)]
        myPriorityQueue = PriorityQueue()
        for i in range(n):
            i = random.randint(0, 100)
            myPriorityQueue.push(i)

        return myPriorityQueue

def main():
    myQueue = PriorityQueue.createFromList([12, 9, 3, 14, 29, 4, 5, 13, 18])
    print(myQueue)
    myQueue.push(7)
    print(myQueue)
    print(len(myQueue)) 
    print(myQueue.pop())
    print(myQueue) 
    my2Queue = PriorityQueue.createRandomPriorityQueue(7)
    print(my2Queue)
    
if __name__ == '__main__':
    doctest.testmod()
    main()

class BinaryTree:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

    def preorder(self):
        """In a preorder traversal, the root node is visited first, followed by the left tree, then the right tree. [8, 3, 1, 6, 4, 7, 10, 14, 13]"""
        result = []
        result.append(self.data)
        if self.left is not None:
            result += self.left.preorder()
        if self.right is not None:
            result += self.right.preorder()
        return result

    def inorder(self):
        """In an inorder traversal, the left tree is visited first, followed by the root node, then followed by the right tree."""
        result = []
        if self.left is not None:
            result += self.left.inorder()
        result.append(self.data)
        if self.right is not None:
            result += self.right.inorder()
        return result

    def postorder(self):
        """In a postorder traversal, the left tree is visited first, followed by the right tree, then the root node. [1, 4, 7, 6, 3, 13, 14, 10, 8]"""
        result = []
        if self.left is not None:
            result += self.left.postorder()
        if self.right is not None:
            result += self.right.postorder()
        result.append(self.data)
        return result

    def level(self):
        queue = Queue()
        queue.enqueue(self)

        result = []
        while len(queue) > 0:
            result.append(queue.peek().data)
            myNode = queue.dequeue()

            if myNode.left is not None:
                queue.enqueue(myNode.left)
            if myNode.right is not None:
                queue.enqueue(myNode.right)

        return result

    def __str__(self):
        return str(self.level())

    def reverse_level(self):
        queue = Queue()
        stack = Stack()
        queue.enqueue(self)

        result = []
        while len(queue) > 0:
            myNode = queue.dequeue()

            stack.push(myNode)

            if myNode.right is not None:
                queue.enqueue(myNode.right)
            if myNode.left is not None:
                queue.enqueue(myNode.left)

        while len(stack) > 0:
            node = stack.pop()
            result.append(node.data)

        return result

    def is_leaf(self): # It returns True if the node does not have any child nodes and returns False otherwise
        return (self.left is None) and (self.right is None)

    def add_child(self, value): # When looking for a place to insert a new "value", we need to traverse the tree from root to leaf, making comparisons to the values of the tree's nodes and deciding based on these comparisons to continue searching in the left or right subtrees.
        if value == self.data:
            return
        if value < self.data:
            if self.left is not None: # We need to continue searching in the left subtree.
                self.left.add_child(value)
            else: # If value is smaller than the current node's data and the current node does not have any left child, then we have found its place.
                self.left = BinaryTree(value)
        else:
            if self.right is not None:
                self.right.add_child(value)
            else:
                self.right = BinaryTree(value)

    @classmethod
    def build_tree(cls, values): # It builds a tree from a list representation
        myTree = BinaryTree(values[0])

        for i in range(1, len(values)):
            myTree.add_child(values[i])

        return myTree

   def print_tree(self, traversal_type):
        if traversal_type == "preorder":
            return self.preorder()
        elif traversal_type == "inorder":
            return self.inorder()
        elif traversal_type == "postorder":
            return self.postorder()
        elif traversal_type == "level":
            return self.level()
        elif traversal_type == "reverse_level":
            return self.reverse_level()
        else:
            print("Traversal type " + str(traversal_type) + " not recognized.")
            return False

    def height(self): # _The height of a binary tree is the maximum depth of the tree_, that is, the distance from the root node to its furthest leaf.
        if self is None:
            return 0
        if self.is_leaf():
            return 1
        else:
            leftHeight, rightHeight = 0, 0
            if self.left is not None:
                leftHeight = self.left.height()
            if self.right is not None:
                rightHeight = self.right.height()
            return 1 + max(leftHeight, rightHeight)

    def size(self): # The size of a binary tree is the number of nodes in it. 
        if self is None:
            return 0
        if self.is_leaf():
            return 1
        leftSize, rightSize = 0, 0
        if self.left is not None:
            leftSize = self.left.size()
        if self.right is not None:
            rightSize = self.right.size()
        return 1 + leftSize + rightSize
    
    def find(self, value):
    """To find value, we need to traverse the tree from root to leaf, making comparisons to the values of the tree's nodes and deciding based on these comparisons to continue searching in the left or right subtrees. If the value at the current node is less than the search target, then we need to search to the right, so we recursively proceed down the right subtree, else if it’s greater than the search target, then we will need to go down the left subtree.""" 
        if self is None:
            return False
        if self.data == value:
            return True
        elif (value < self.data and self.left is not None):
            return self.left.find(value)
        elif (value > self.data and self.right is not None):
            return self.right.find(value)
        else:
            return False

    def delete(self, value):
    """First, we should proceed the same as before, we need to traverse the tree, making comparisons to the values of the tree's nodes and deciding based on these comparisons to continue searching in the left or right subtrees.""" 
        if value < self.data:
            if self.left is not None:
                self.left = self.left.delete(value)
        elif value > self.data:
            if self.right is not None:
                self.right = self.right.delete(value)
        else: # We have already found it!
            if self.is_leaf(): # If the node is a leaf node, we just return None.
                return None
            elif self.left is None: # If the node does have one single child, say the right child, we return it. In other words, its child takes its position.
                return self.right
            elif self.right is None:
                return self.left
            # This is the tricky part, the node has two children. We need to find the minimum value in its right subtree (1), copy its value (2), and remove the duplicate (3). 
            min_value = self.right.find_min() # (1)
            self.data = min_value # (2)
            self.right = self.right.delete(min_value) # (3)

        return self

    def find_min(self):
        if self.left is None:
            return self.data
        return self.left.find_min()

def main():
    tree = BinaryTree.build_tree([8, 3, 10, 1, 6, 14, 4, 7, 13])
    print(tree.print_tree("level")) # [8, 3, 10, 1, 6, 14, 4, 7, 13]
    print(tree.print_tree("preorder")) # [8, 3, 1, 6, 4, 7, 10, 14, 13]
    print(tree.print_tree("inorder")) # [1, 3, 4, 6, 7, 8, 10, 13, 14]
    print(tree.print_tree("postorder")) # [1, 4, 7, 6, 3, 13, 14, 10, 8]
    print(tree.print_tree("reverse_level")) # [4, 7, 13, 1, 6, 14, 3, 10, 8]
    print(tree.height()) # 4
    print(tree.size()) # 9
    print(tree.find(6)) # True
    print(tree.find(13)) # True
    print(tree.find(2)) # False
    print(tree.find_min()) # 1
    print(tree.is_leaf()) # False
    tree.delete(7)
    tree.delete(3)
    print(tree) # [8, 4, 10, 1, 6, 14, 13]
if __name__ == '__main__':
    main()

 def is_balanced(self):
        if self is None:
            return True
        if self.is_leaf():
            return True
        if self.right is None:
            return self.left.height() <= 1
        if self.left is None:
            return self.right.height() <= 1
        return self.right.is_balanced() and self.left.is_balanced() and abs(self.left.height() - self.right.height()) <= 1

def main():
    tree = BinaryTree.build_tree([8, 3, 10, 1, 6, 14, 4, 7, 13]) # [8, 3, 10, 1, 6, 14, 4, 7, 13]
    print(tree.is_balanced()) # False
    tree.add_child(9) # [8, 3, 10, 1, 6, 9, 14, 4, 7, 13]
    print(tree.is_balanced()) # True
if __name__ == '__main__':
    main()