Linked List, Stack, Queue, functions to traverse Trees

linkedListStackQueueTree.py

'''Course: https://www.coursera.org/learn/data-structures#about'''


class Node:

    def __init__(self, key, next=None):
        self.key = key
        self.next = next


class SinglyLinkedList:
    '''O(1) to remove first element (O(n) for list/array).
    O(n) for popBack()'''

    def __init__(self):
        self.head = None
        self.tail = None


    def pushFront(self, key):
        node = Node(key=key, next=self.head)
        self.head = node

        if self.tail == None:
            self.tail = self.head


    def topFront(self):
        return self.head.key


    def popFront(self):
        if self.head == None:
            raise Exception("Empty list")

        poppedKey = self.head.key
        self.head = self.head.next

        if self.head == None:
            self.tail = None

        return poppedKey



    def pushBack(self, key):
        node = Node(key=key)

        if self.tail == None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node



    def popBack(self):
        if self.head == None:
            raise Exception("Empty list")

        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            head = self.head
            while head.next.next != None:
                head = head.next

            head.next = None
            self.tail = head


    def addAfter(self, node, key):
        node2 = Node(key=key, next=node.next)
        node.next = node2

        if self.tail == node:
            self.tail = node2


    def empty(self):
        return self.head == None



    def __str__(self):
        head = self.head
        string = "["+str(head.key) + ", "

        while head.next.next != None:
            head = head.next
            string += str(head.key) + ", "

        string += str(head.next.key) + "]"
        return string





class NodeForDoublyLinkedList:

    def __init__(self, key, next=None, previous=None):
        self.key = key
        self.next = next
        self.previous = previous




class DoublyLinkedList:
    '''O(1) for popBack() and addBefore()'''

    def __init__(self):
        self.head = None
        self.tail = None


    def pushBack(self, key):
        node = NodeForDoublyLinkedList(key=key)

        if self.tail == None:
            self.head = node
            self.tail = node
            node.previous = None
        else:
            self.tail.next = node
            node.previous = self.tail
            self.tail = node


    def popBack(self):
        if self.head == None:
            raise Exception("Empty list")

        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.previous
            self.tail.next = None



    def addAfter(self, node, key):
        node2 = NodeForDoublyLinkedList(key=key, next=node.next, previous=node)
        node.next = node2

        if node2.next != None:
            node2.next.previous = node2

        if self.tail == node:
            self.tail = node2


    def addBefore(self, node, key):
        node2 = NodeForDoublyLinkedList(key=key, next=node, previous=node.previous)
        node.previous = node2

        if node2.previous != None:
            node2.previous.next = node2

        if self.head == node:
            self.head = node2


    def __str__(self):
        head = self.head
        string = "["+str(head.key) + ", "

        while head.next.next != None:
            head = head.next
            string += str(head.key) + ", "

        string += str(head.next.key) + "]"
        return string




class StackUsingArray:

    defaultArraySize = 5

    def __init__(self, size=None):
        self.size = size if size != None else StackUsingArray.defaultArraySize
        self.numOfElements = 0
        self.array = [None] * self.size


    def push(self, key):
        if self.numOfElements == self.size:
            raise Exception("No space in stack")

        self.array[self.numOfElements] = key
        self.numOfElements += 1


    def top(self):
        if self.numOfElements == 0:
            raise Exception("Stack is empty")
        return self.array[self.numOfElements - 1]


    def pop(self):
        if self.numOfElements == 0:
            raise Exception("Stack is empty")

        self.numOfElements -= 1
        return self.array[self.numOfElements]


    def empty(self):
        return self.numOfElements == 0





class StackUsingLinkedList:

    def __init__(self):
        self.collection = SinglyLinkedList()

    def push(self, key):
        self.collection.pushFront(key)

    def top(self):
        return self.collection.topFront()

    def pop(self):
        return self.collection.popFront()

    def empty(self):
        return self.collection.empty()





def isBalanced(string):
    '''returns false if there brackets in string are unbalanced.
    Balanced: '([])'
    Unbalanced: '([)]' or ']()]' or '[])('...'''

    stack = StackUsingLinkedList()

    for char in string:

        if char in ['(', '[']:
            stack.push(char)
        else:
            if stack.empty(): return False

            top = stack.pop()
            if (top == '[' and char != ']') or (top == '(' and char != ')'):
                return False

    return stack.empty()




class QueueUsingLinkedList:

    def __init__(self):
        self.collection = SinglyLinkedList()

    def enqueue(self, key):
        self.collection.pushBack(key)

    def dequeue(self):
        return self.collection.popFront()

    def empty(self):
        return self.collection.empty()




class QueueUsingArray:

    defaultArraySize = 5

    def __init__(self, size=None):
        self.size = size if size != None else StackUsingArray.defaultArraySize
        self.array = [None] * self.size
        self.read = 0
        self.write = 0


    def enqueue(self, key):

        if self.read - self.write == 1:
            raise Exception("No space in Queue")

        if self.write == self.size:
            self.write = 0

        self.array[self.write] = key
        self.write += 1


    def dequeue(self):

        if self.read == self.write:
            raise Exception("Stack is empty")

        if self.read == self.size:
            self.read = 0

        element = self.array[self.read]
        self.read += 1
        return element


    def empty(self):
        return self.read == self.write




class NodeForTree:

    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right



def insertLeftChild(node, key):
    node2 = NodeForTree(key=key)
    node.left = node2
    return node2


def insertRightChild(node, key):
    node2 = NodeForTree(key=key)
    node.right = node2
    return node2




def heightOfTree(tree):

    if tree == None:
        return 0
    return 1 + max(heightOfTree(tree.left), heightOfTree(tree.right))



def sizeOfTree(tree):

    if tree == None:
        return 0
    return 1 + sizeOfTree(tree.left) + sizeOfTree(tree.right)



def inOrderTraversalOfTree(tree):
    '''depth-first'''

    if tree == None:
        return

    inOrderTraversalOfTree(tree.left)
    print(tree.key)
    inOrderTraversalOfTree(tree.right)



def preOrderTraversalOfTree(tree):
    '''depth-first'''

    if tree == None:
        return

    print(tree.key)
    preOrderTraversalOfTree(tree.left)
    preOrderTraversalOfTree(tree.right)



def postOrderTraversalOfTree(tree):
    '''depth-first'''

    if tree == None:
        return

    postOrderTraversalOfTree(tree.left)
    postOrderTraversalOfTree(tree.right)
    print(tree.key)



def leveltraversalOfTree(tree):
    '''breadth-first'''

    if tree == None:
        return

    queue = QueueUsingLinkedList()
    queue.enqueue(tree)

    while not queue.empty():
        node = queue.dequeue()
        print(node.key)

        if node.left != None:
            queue.enqueue(node.left)

        if node.right != None:
            queue.enqueue(node.right)







if __name__ == "__main__":

    print("\nSingly LinkedList: ")
    singlyLinkedList = SinglyLinkedList()
    singlyLinkedList.pushFront(4)
    singlyLinkedList.pushFront(3)
    singlyLinkedList.pushFront(2)
    singlyLinkedList.pushFront(1)
    singlyLinkedList.pushBack(5)
    print(singlyLinkedList)


    print("\nDoubly LinkedList: ")
    doublyLinkedList = DoublyLinkedList()
    doublyLinkedList.pushBack(5)
    doublyLinkedList.pushBack(4)
    doublyLinkedList.pushBack(3)
    doublyLinkedList.pushBack(2)
    doublyLinkedList.pushBack(1)
    doublyLinkedList.popBack()
    print(doublyLinkedList)


    print("\nStack using Array:")
    stackUsingArray = StackUsingArray()
    print(stackUsingArray.empty())
    stackUsingArray.push(1)
    stackUsingArray.push(2)
    stackUsingArray.push(3)
    stackUsingArray.push(4)
    stackUsingArray.push(5)
    print(stackUsingArray.pop())
    print(stackUsingArray.pop())
    print(stackUsingArray.empty())


    print("\nStack using Linked List:")
    stackUsingLinkedList = StackUsingLinkedList()
    print(stackUsingLinkedList.empty())
    stackUsingLinkedList.push(1)
    stackUsingLinkedList.push(2)
    stackUsingLinkedList.push(3)
    stackUsingLinkedList.push(4)
    stackUsingLinkedList.push(5)
    print(stackUsingLinkedList.pop())
    print(stackUsingLinkedList.pop())
    print(stackUsingLinkedList.empty())


    print("\nCheck if brackets in string (([])) are balanced:", isBalanced('(([]))'))


    print("\nQueue using Linked List:")
    queueUsingLinkedList = QueueUsingLinkedList()
    print(queueUsingLinkedList.empty())
    queueUsingLinkedList.enqueue(1)
    queueUsingLinkedList.enqueue(2)
    queueUsingLinkedList.enqueue(3)
    queueUsingLinkedList.enqueue(4)
    queueUsingLinkedList.enqueue(5)
    print(queueUsingLinkedList.dequeue())
    print(queueUsingLinkedList.dequeue())
    print(queueUsingLinkedList.empty())



    print("\nQueue using Array:")
    queueUsingArray = QueueUsingArray()
    print(queueUsingArray.empty())
    queueUsingArray.enqueue(1)
    queueUsingArray.enqueue(2)
    print(queueUsingArray.dequeue())
    print(queueUsingArray.dequeue())
    queueUsingArray.enqueue(3)
    queueUsingArray.enqueue(4)
    queueUsingArray.enqueue(5)
    queueUsingArray.enqueue(6)
    print(queueUsingArray.empty())



    print("\nTree:")
    nodeLes = NodeForTree(key='Les')
    nodeCathy = insertLeftChild(nodeLes, 'Cathy')
    insertLeftChild(nodeCathy, 'Alex')
    insertRightChild(nodeCathy, 'Frank')

    nodeSam = insertRightChild(nodeLes, 'Sam')
    insertLeftChild(nodeSam, 'Nancy')

    nodeViolet = insertRightChild(nodeSam, 'Violet')
    insertLeftChild(nodeViolet, 'Tony')
    insertRightChild(nodeViolet, 'Wendy')


    print("Height of the tree:", heightOfTree(nodeLes))
    print("Size of the tree:", sizeOfTree(nodeLes))
    print("\nInOrder traversal:")
    inOrderTraversalOfTree(nodeLes)
    print("\nPreOrder traversal:")
    preOrderTraversalOfTree(nodeLes)
    print("\nPostOrder traversal:")
    postOrderTraversalOfTree(nodeLes)
    print("\nLevel traversal:")
    leveltraversalOfTree(nodeLes)