//Binary Tree bedb class Node: def __init__(self, data): self.data = data self.left = None self.right = None self.parent = None

def isLeafNode(self):
    if self is None:
        return False
    if self.left is None and self.right is None:
        return True
    else:
        return False

def isInternalNode(self):
    if self is None:
        return False
    if self.left is not None or self.right is not None:
        return True
    else:
        return False

def isExternalNode(self):
    if self is None:
        return False
    if self.left is None and self.right is None:
        return True
    else:
        return False

def isLeftNode(self):
    if self is None:
        return False
    if self.parent is None:
        return False
    if self.parent.left is None:
        return False
    if self.parent.left == self:
        return True
    else:
        return False

class BST: def __init__(self): self.root = None self.size = 0

def insert(self, data):
    if self.root is None:
        self.root = Node(data)
        self.size += 1
    else:
        # Iterative
        currentNode = self.root
        while True:
            if data <= currentNode.data:
                if currentNode.left is None:
                    currentNode.left = Node(data)
                    currentNode.left.parent = currentNode
                    self.size += 1
                    break
                else:
                    currentNode = currentNode.left
            elif data > currentNode.data:
                if currentNode.right is None:
                    currentNode.right = Node(data)
                    currentNode.right.parent = currentNode
                    self.size += 1
                    break
                else:
                    currentNode = currentNode.right

def inOrder(self, node):
    if node is None:
        return []

    return self.inOrder(node.left) + [node.data] + self.inOrder(node.right)

def preOrder(self, node):
    if node is None:
        return []

    return [node.data] + self.preOrder(node.left) + self.preOrder(node.right)

def postOrder(self, node):
    if node is None:
        return []

    return self.postOrder(node.left) + self.postOrder(node.right) + [node.data]

def search(self, data):
    if self.root is None:
        return False
    else:
        currentNode = self.root
        while True:
            if currentNode is None:
                return False
            elif data == currentNode.data:
                return True
            elif data < currentNode.data:
                currentNode = currentNode.left
            elif data > currentNode.data:
                currentNode = currentNode.right

def height(self, node):
    if node is None:
        return -1
    else:
        leftHeight = self.height(node.left)
        rightHeight = self.height(node.right)
        return max(leftHeight, rightHeight) + 1

def isBalanced(self, node):
    if node is None:
        return True
    else:
        leftHeight = self.height(node.left)
        rightHeight = self.height(node.right)

        if abs(leftHeight - rightHeight) <= 1 and self.isBalanced(node.left) and self.isBalanced(node.right):
            return True
        else:
            return False

def levelOrder(self, node):
    if node is None:
        return []

    queue = []
    queue.append(node)
    queue.append(None)

    levelOrderList = [[]]
    level = 0

    while len(queue) > 0:
        currentNode = queue.pop(0)
        if currentNode is None:
            level += 1
            if len(queue) > 0:
                levelOrderList.append([])
                queue.append(None)
        else:
            levelOrderList[level].append(currentNode.data)

            if currentNode.left is not None:
                queue.append(currentNode.left)
            if currentNode.right is not None:
                queue.append(currentNode.right)

    return levelOrderList

# Level Order starts from 1
def getNodesAtLevel(self, level):
    if self.root is None:
        return []
    else:
        levelOrderList = self.levelOrder(self.root)
        if level > len(levelOrderList):
            return []
        else:
            return levelOrderList[level-1]

def spiralOrder(self, node):
    if node is None:
        return []
    else:
        levelOrderList = self.levelOrder(node)
        spiralOrderList = []
        for i in range(len(levelOrderList)):
            if i % 2 != 0:
                levelOrderList[i].reverse()
            spiralOrderList.append(levelOrderList[i])
        return spiralOrderList

def mirrorImage(self, node):
    if node is None:
        return
    else:
        levelOrderList = self.levelOrder(node)
        for i in range(len(levelOrderList)):
            levelOrderList[i].reverse()
        return levelOrderList

def lowestCommonAncestor(self, nodeA, nodeB):
    if self.root is None:
        return None
    else:
        if self.search(nodeA) == False or self.search(nodeB) == False:
            return None
        currentNode = self.root
        while True:
            if currentNode.data > nodeA and currentNode.data > nodeB:
                currentNode = currentNode.left
            elif currentNode.data < nodeA and currentNode.data < nodeB:
                currentNode = currentNode.right
            else:
                return currentNode.data

def greatestCommonAncestor(self, nodeA, nodeB):
    if not self.search(nodeA) or not self.search(nodeB):
        return None

    currentNode = self.root
    if nodeA <= currentNode.data and nodeB <= currentNode.data:
        return self.root.data
    if nodeA > currentNode.data and nodeB > currentNode.data:
        return self.lowestCommonAncestor(nodeA, nodeB)

    return self.root.data

def kThMinimum(self, k):
    if self.root is None or k >= self.size:
        return None

    return self.inOrder(self.root)[k - 1]

def kThMaximum(self, k):
    if self.root is None or k >= self.size:
        return None

    inOrder = self.inOrder(self.root)
    inOrder.reverse()

    return inOrder[k-1]

def levelOrderNodeList(self, node):
    if node is None:
        return []
    else:
        queue = []
        queue.append(node)
        queue.append(None)

        levelOrderList = [[]]
        level = 0

        while len(queue) > 0:
            currentNode = queue.pop(0)
            if currentNode is None:
                level += 1
                if len(queue) > 0:
                    levelOrderList.append([])
                    queue.append(None)
            else:
                levelOrderList[level].append(currentNode)

                if currentNode.left is not None:
                    queue.append(currentNode.left)
                if currentNode.right is not None:
                    queue.append(currentNode.right)

        return levelOrderList

def deepestLeftLeaf(self, node : Node):
    levelOrder = self.levelOrderNodeList(node)
    if levelOrder is {}:
        return None
    for level in range(len(levelOrder) - 1, -1, -1):
        for node in levelOrder[level]:
            if node.isLeafNode() and node.isLeftNode():
                return node.data

    return None

bst = BST() bst.insert(10) bst.insert(5) bst.insert(15) bst.insert(3) bst.insert(7) bst.insert(12) bst.insert(17) bst.insert(16) bst.insert(18)

print("In Order: ", bst.inOrder(bst.root)) print("Pre Order: ", bst.preOrder(bst.root)) print("Post Order: ", bst.postOrder(bst.root)) print("Search 10: ", bst.search(10)) print("Height: ", bst.height(bst.root)) print("Is Balanced: ", bst.isBalanced(bst.root)) print("Level Order: ", bst.levelOrder(bst.root)) print("Nodes at Level 3: ", bst.getNodesAtLevel(3)) print("Spiral Order: ", bst.spiralOrder(bst.root)) print("Mirror Image: ", bst.mirrorImage(bst.root)) print("Lowest Common Ancestor of 3 and 7: ", bst.lowestCommonAncestor(3, 7)) print("Greatest Common Ancestor of 3 and 7: ", bst.greatestCommonAncestor(3, 7)) print("Kth Minimum (k = 3): ", bst.kThMinimum(3)) print("Kth Maximum (k = 3): ", bst.kThMaximum(3)) print("Deepest Left Leaf: ", bst.deepestLeftLeaf(bst.root)) //

//Binary Tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None self.parent = None

class BinaryTree: def __init__(self): self.root = None self.size = 0

def buildTreeFromPreIn(self, preOrder, inOrder):
    if len(preOrder) == 0:
        return None

    root = Node(preOrder[0])
    rootIndex = inOrder.index(preOrder[0])

    root.left = self.buildTreeFromPreIn(preOrder[1:rootIndex+1], inOrder[:rootIndex])
    root.right = self.buildTreeFromPreIn(preOrder[rootIndex+1:], inOrder[rootIndex+1:])

    return root

def buildTreeFromPostIn(self, post, ino):
    if len(post) == 0:
        return None

    root = Node(post[-1])
    rootIndex = ino.index(post[-1])

    root.left = self.buildTreeFromPostIn(post[:rootIndex], ino[:rootIndex])
    root.right = self.buildTreeFromPostIn(post[rootIndex:-1], ino[rootIndex+1:])

    return root


def inOrder(self, node):
    if node is None:
        return []
    return self.inOrder(node.left) + [node.data] + self.inOrder(node.right)

def preOrder(self, node):
    if node is None:
        return []
    return [node.data] + self.preOrder(node.left) + self.preOrder(node.right)

def postOrder(self, node):
    if node is None:
        return []
    return self.postOrder(node.left) + self.postOrder(node.right) + [node.data]

preOrder = [1, 2, 4, 5, 3, 6, 7] inOrder = [4, 2, 5, 1, 6, 3, 7]

treeA = BinaryTree() treeA.root = treeA.buildTreeFromPreIn(preOrder, inOrder)

print("InOrder: ", treeA.inOrder(treeA.root)) print("PreOrder: ", treeA.preOrder(treeA.root)) print("PostOrder: ", treeA.postOrder(treeA.root))

print("====================================")

postOrder = [4, 5, 2, 6, 7, 3, 1] inOrder = [4, 2, 5, 1, 6, 3, 7]

treeB = BinaryTree() treeB.root = treeB.buildTreeFromPostIn(postOrder, inOrder)

print("InOrder: ", treeB.inOrder(treeB.root)) print("PreOrder: ", treeB.preOrder(treeB.root)) print("PostOrder: ", treeB.postOrder(treeB.root))

//

//BTGHU import collections class Node: def __init__(self, data): self.right = None self.left = None self.data = data

def insert(self, data):
    if self.data is None:
        self.data = data
    else:
        if self.data > data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        elif self.data < data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)

def inorderprint(r): if r: inorderprint(r.left) print(r.data ,end=' ') inorderprint(r.right)

def preorderprint(r): if r: print(r.data,end=' ') preorderprint(r.left) preorderprint(r.right)

def postorderprint(r): if r: postorderprint(r.left) postorderprint(r.right) print(r.data,end=' ')

def adjacencylist(r): if r: d[r.data]=[] adjacencylist(r.left) if r.left: d[r.data].append(r.left.data) if r.right: d[r.data].append(r.right.data) adjacencylist(r.right) return d

def BFS(r): queue=collections.deque([r]) visited=[] while queue: node=queue.popleft() visited.append(node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right) print(visited)

if __name__ == "__main__": root = Node('g') root.insert('c') root.insert('i') root.insert('b') root.insert('e') root.insert('a') root.insert('d') root.insert('f') root.insert('h') root.insert('j') root.insert('k') d={}

#inorderprint(root)
#preorderprint(root)
#postorderprint(root)
adl=adjacencylist(root)
for ele in adl:
    print(f'{ele}:{d[ele]}')
print(adl)
BFS(root)

del funct: def find_min_value_node(node): current = node while current.left is not None: current = current.left return current

def delete_node(root, key): if root is None: return root

if key < root.data:
    root.left = delete_node(root.left, key)
elif key > root.data:
    root.right = delete_node(root.right, key)
else:
    if root.left is None:
        temp = root.right
        root = None
        return temp
    elif root.right is None:
        temp = root.left
        root = None
        return temp

    temp = find_min_value_node(root.right)
    root.data = temp.data
    root.right = delete_node(root.right, temp.data)

    return root

//Heap class MinHeap: def __init__(self): self.heap = []

def heapify(self, i):
    l = 2*i + 1
    r = 2*i + 2
    smallest = i

    if l < len(self.heap) and self.heap[l] < self.heap[smallest]:
        smallest = l
    if r < len(self.heap) and self.heap[r] < self.heap[smallest]:
        smallest = r

    if smallest != i:
        self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
        self.heapify(smallest)

def build_heap(self, arr):
    self.heap = arr
    for i in range(len(self.heap) // 2 - 1, -1, -1):
        self.heapify(i)

def insert(self, data):
    self.heap.append(data)
    i = len(self.heap) - 1

    while i > 0:
        parent = (i - 1) // 2
        if self.heap[i] < self.heap[parent]:
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
        else:
            break

def extract_min(self):
    if len(self.heap) == 0:
        return None

    self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
    heap_min = self.heap.pop()
    self.heapify(0)

    return heap_min

def delete(self, data):
    if len(self.heap) == 0:
        return None

    i = self.heap.index(data)
    self.heap[i], self.heap[-1] = self.heap[-1], self.heap[i]
    self.heap.pop()
    self.heapify(i)


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

class MaxHeap: def __init__(self): self.heap = []

def heapify(self, i):
    l = 2*i + 1
    r = 2*i + 2
    largest = i

    if l < len(self.heap) and self.heap[l] > self.heap[largest]:
        largest = l
    if r < len(self.heap) and self.heap[r] > self.heap[largest]:
        largest = r

    if largest != i:
        self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
        self.heapify(largest)

def build_heap(self, arr):
    self.heap = arr
    for i in range(len(self.heap) // 2 - 1, -1, -1):
        self.heapify(i)

def insert(self, data):
    self.heap.append(data)
    i = len(self.heap) - 1

    while i > 0:
        parent = (i - 1) // 2
        if self.heap[i] > self.heap[parent]:
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
        else:
            break

def extract_max(self):
    if len(self.heap) == 0:
        return None

    self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
    heap_max = self.heap.pop()
    self.heapify(0)

    return heap_max

def delete(self, data):
    if len(self.heap) == 0:
        return None

    i = self.heap.index(data)
    self.heap[i], self.heap[-1] = self.heap[-1], self.heap[i]
    self.heap.pop()
    self.heapify(i)


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

if __name__ == "__main__": print("\nMIN HEAP\n") heap = MinHeap() heap.insert(5) heap.insert(3) heap.insert(7) heap.insert(2) heap.insert(1) heap.insert(9) heap.insert(4) heap.insert(6) heap.insert(8)

print("[Heap]:", heap)
heap.delete(3)
print("[Heap]:", heap)

print("[Heap]:", heap)
print("[Extract Min]:", heap.extract_min())
print("[Heap]:", heap)
print("[Extract Min]:", heap.extract_min())
print("[Heap]:", heap)

print("\n\nMAX HEAP\n")

heap = MaxHeap()
heap.insert(5)
heap.insert(3)
heap.insert(7)
heap.insert(2)
heap.insert(1)
heap.insert(9)
heap.insert(4)
heap.insert(6)
heap.insert(8)

print("[Heap]:", heap)
heap.delete(3)
print("[Heap]:", heap)

print("[Extract Max]:", heap.extract_max())
print("[Heap]:", heap)
print("[Extract Max]:", heap.extract_max())
print("[Heap]:", heap)

// //DAG class DAG:

def __init__(self):
    self.aList = {}
    self.size = 0

def isVertex(self, vertex):
    return vertex in self.aList

def numVertices(self):
    return self.size

def numEdges(self):
    return sum([len(self.aList[vertex]) for vertex in self.aList])

def vertices(self):
    vertices = []
    for vertex in self.aList:
        vertices.append(vertex)
    return vertices

def edges(self):
    edges = []
    for vertex in self.aList:
        for v in self.aList[vertex]:
            edges.append((vertex, v))
    return edges

def sortAdjacencyList(self):
    # Sort keys
    self.aList = dict(sorted(self.aList.items()))
    # Sort values
    for vertex in self.aList:
        self.aList[vertex].sort()

def insertVertex(self, vertex):
    if not self.isVertex(vertex):
        self.aList[vertex] = []
        self.size += 1
    else:
        print("Vertex already exists")

def insertEdge(self, edge):
    u, v = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u] and u not in self.aList[v]:
        self.aList[u].append(v)
    else:
        print("Invalid directed edge")

def removeVertex(self, vertex):
    if self.isVertex(vertex):
        for v in self.aList[vertex]:
            self.aList[v].remove(vertex)
        self.aList.pop(vertex)
        self.size -= 1
    else:
        print("Vertex does not exist")

def removeEdge(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        if v in self.aList[u]:
            self.aList[u].remove(v)
        else:
            print("Invalid directed edge")
    else:
        print("Invalid directed edge")

def inDegree(self, vertex):
    if self.isVertex(vertex):
        return sum([1 for v in self.aList if vertex in self.aList[v]])
    else:
        print("Vertex does not exist")

def outDegree(self, vertex):
    if self.isVertex(vertex):
        return len(self.aList[vertex])
    else:
        print("Vertex does not exist")

def degree(self, vertex):
    if self.isVertex(vertex):
        return self.inDegree(vertex) + self.outDegree(vertex)
    else:
        print("Vertex does not exist")

def neighbors(self, vertex):
    if self.isVertex(vertex):
        return self.aList[vertex]
    else:
        print("Vertex does not exist")

def adjacent(self, u, v):
    if self.isVertex(u) and self.isVertex(v):
        return v in self.aList[u]
    else:
        print("Invalid directed edge")

def DFS(self, start_vertex):
    visited = {}
    for v in self.aList:
        visited[v] = False

    dfs = []

    def DFS_visit(vertex):
        visited[vertex] = True
        dfs.append(vertex)
        for v in self.aList[vertex]:
            if not visited[v]:
                DFS_visit(v)

    DFS_visit(start_vertex)

    return dfs

def BFS(self, start_vertex):
    visited = {}
    for v in self.aList:
        visited[v] = False

    bfs = []
    queue = [start_vertex]

    while queue:
        vertex = queue.pop(0)
        if not visited[vertex]:
            visited[vertex] = True
            bfs.append(vertex)
            for v in self.aList[vertex]:
                queue.append(v)

    return bfs

def DFS_spanning_tree(self, start_vertex):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    spanning_tree = {}

    def DFS_visit(vertex):
        visited[vertex] = True
        for v in self.aList[vertex]:
            if not visited[v]:
                spanning_tree[v] = vertex
                DFS_visit(v)

    DFS_visit(start_vertex)
    return spanning_tree

def BFS_spanning_tree(self, start_vertex):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    spanning_tree = {}
    queue = [start_vertex]

    while queue:
        vertex = queue.pop(0)
        if not visited[vertex]:
            visited[vertex] = True
            for v in self.aList[vertex]:
                if not visited[v]:
                    spanning_tree[v] = vertex
                    queue.append(v)

    return spanning_tree

def topological_sort(self):
    """
        1. Compute the in-degree of each node in the graph.
        2. Enqueue all nodes with in-degree 0 to a queue.
        3. While the queue is not empty, dequeue a node from the front of the queue and add it to the sorted list.
        4. For each of the dequeued node's neighbors, decrement their in-degree by 1.
        5. If any of the dequeued node's neighbors now have in-degree 0, enqueue them to the queue.
        6. Repeat steps 3-5 until the queue is empty.
    """
    in_degrees = {}
    for vertex in self.vertices():
        in_degrees[vertex] = self.inDegree(vertex)

    topological_order = []
    queue = []

    for vertex in in_degrees:
        if in_degrees[vertex] == 0:
            queue.append(vertex)

    while queue:
        vertex = queue.pop(0)
        topological_order.append(vertex)
        for v in self.aList[vertex]:
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                queue.append(v)

    return topological_order

def isDAG(self):
    spanning_tree = self.DFS_spanning_tree(self.vertices()[0])
    for vertex in spanning_tree:
        if spanning_tree[vertex] == vertex:
            return False
    return True

def longestPath(self):
    in_degrees = {}
    longest_paths = {}
    for v in self.aList:
        in_degrees[v] = self.inDegree(v)
        longest_paths[v] = 0
    queue = []

    for v in in_degrees:
        if in_degrees[v] == 0:
            queue.append(v)

    while queue:
        vertex = queue.pop(0)
        for v in self.aList[vertex]:
            if longest_paths[v] < longest_paths[vertex] + 1:
                longest_paths[v] = longest_paths[vertex] + 1
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                queue.append(v)

    return longest_paths

g = DAG()

edgeList = [ (1, 2), (1, 7), (2, 5), (0, 2), (0, 3), (0, 4), (3, 5), (3, 7), (6, 7), (5, 6), (4, 7) ]

for edge in edgeList: g.insertEdge(edge)

g.sortAdjacencyList() print("\n") print("Vertices:", g.vertices()) print("Edges:", g.edges()) print("Size:", g.size) print("Adjacency List:", g.aList) print("DFS:", g.DFS(0)) print("BFS:", g.BFS(0)) print("DFS Spanning Tree:", g.DFS_spanning_tree(0)) print("BFS Spanning Tree:", g.BFS_spanning_tree(0)) print("Is DAG:", g.isDAG()) print("Topological Sort:", g.topological_sort()) print("Longest Path:", g.longestPath()) // //CG class Graph: def __init__(self): self.aList = {} self.size = 0

def isVertex(self, vertex):
    return vertex in self.aList

def numVertices(self):
    return self.size

def numEdges(self):
    return sum([len(self.aList[vertex]) for vertex in self.aList])

def vertices(self):
    vertices = []
    for vertex in self.aList:
        vertices.append(vertex)
    return vertices

def edges(self):
    edges = []
    for vertex in self.aList:
        for v in self.aList[vertex]:
            edges.append((vertex, v))
    return edges

def sortAdjacencyList(self):
    # Sort keys
    self.aList = dict(sorted(self.aList.items()))
    # Sort values
    for vertex in self.aList:
        self.aList[vertex].sort()

def insertVertex(self, vertex):
    if not self.isVertex(vertex):
        self.aList[vertex] = []
        self.size += 1
    else:
        print("Vertex already exists")

def insertEdge(self, edge):
    u, v = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u]:
        self.aList[u].append(v)
    else:
        print(f"Edge ({u}, {v}) already exists")
    if u not in self.aList[v]:
        self.aList[v].append(u)
    else:
        print(f"Edge ({v}, {u}) already exists")

def insertDirectedEdge(self, edge):
    u, v = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u] and u not in self.aList[v]:
        self.aList[u].append(v)
    else:
        print("Invalid directed edge")

def removeVertex(self, vertex):
    if self.isVertex(vertex):
        for v in self.aList[vertex]:
            self.aList[v].remove(vertex)
        self.aList.pop(vertex)
        self.size -= 1
    else:
        print("Vertex does not exist")

def removeEdge(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        if v in self.aList[u]:
            self.aList[u].remove(v)
        if u in self.aList[v]:
            self.aList[v].remove(u)
    else:
        print("Edge does not exist")

def incidentEdges(self, vertex):
    if self.isVertex(vertex):
        return [(vertex, v) for v in self.aList[vertex]]
    else:
        print("Vertex does not exist")

def degree(self, vertex):
    if self.isVertex(vertex):
        return len(self.aList[vertex])
    else:
        print("Vertex does not exist")

def endVertices(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        if v in self.aList[u] and u in self.aList[v]:
            return (u, v)
    else:
        print("Edge does not exist")

def isDirected(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        return v in self.aList[u] and u not in self.aList[v]
    else:
        print("Edge does not exist")

def isOrigin(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        return v in self.aList[u] and u not in self.aList[v]
    else:
        print("Edge does not exist")

def isDestination(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        return u in self.aList[v] and v not in self.aList[u]
    else:
        print("Edge does not exist")

def opposite(self, vertex, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        if vertex == u:
            return v
        elif vertex == v:
            return u
        else:
            print("Vertex is not incident to edge")
    else:
        print("Edge does not exist")

def areAdjacent(self, edgeA, edgeB):
    uA, vA = edgeA
    uB, vB = edgeB
    if self.isVertex(uA) and self.isVertex(vA) and self.isVertex(uB) and self.isVertex(vB):
        return (uA, vA) in self.aList[uB] and (uA, vA) in self.aList[vB]
    else:
        print("Edge does not exist")

def DFS(self, start_vertex):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    dfs = []

    def DFS_visit(vertex):
        visited[vertex] = True
        dfs.append(vertex)
        for v in self.aList[vertex]:
            if not visited[v]:
                DFS_visit(v)

    DFS_visit(start_vertex)
    return dfs

def DFS_spanning_tree(self, start_vertex):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    spanning_tree = {}

    def DFS_visit(vertex):
        visited[vertex] = True
        for v in self.aList[vertex]:
            if not visited[v]:
                spanning_tree[v] = vertex
                DFS_visit(v)

    DFS_visit(start_vertex)
    return spanning_tree

def BFS(self, start_vertex):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    bfs = []

    queue = [start_vertex]

    while queue:
        vertex = queue.pop(0)
        if not visited[vertex]:
            visited[vertex] = True
            bfs.append(vertex)
            for v in self.aList[vertex]:
                queue.append(v)

    return bfs

def BFS_spanning_tree(self, start_vertex):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    spanning_tree = {}

    queue = [start_vertex]

    while queue:
        vertex = queue.pop(0)
        if not visited[vertex]:
            visited[vertex] = True
            for v in self.aList[vertex]:
                if not visited[v]:
                    spanning_tree[v] = vertex
                    queue.append(v)
    return spanning_tree

# DFS Applications
def findPath(self, start_vertex, end_vertex):
    spanning_tree = self.DFS_spanning_tree(start_vertex)
    path = []
    if end_vertex in spanning_tree:
        path.append(end_vertex)
        while path[-1] != start_vertex:
            path.append(spanning_tree[path[-1]])
        path.reverse()
    return path

def detectCycleDFS(self):
    """
    The idea behind the function is to perform a depth-first search starting from each unvisited vertex in the graph. During the DFS traversal, if a vertex is encountered that has already been visited, it implies that there is a cycle in the graph. The function immediately returns "True" in that case.

    Finding a backward edge in other words.

    If the DFS traversal is completed without encountering a cycle, the function returns "False".
    """
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    def DFS_visit(vertex):
        visited[vertex] = True
        for v in self.aList[vertex]:
            if not visited[v]:
                DFS_visit(v)
            else:
                return True
        return False

    for vertex in self.vertices():
        if not visited[vertex]:
            if DFS_visit(vertex):
                return True
    return False



# BFS Applications
def findConnectedComponents(self):
    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    connected_components = []

    for vertex in self.vertices():
        if not visited[vertex]:
            connected_component = self.BFS(vertex)
            connected_components.append(connected_component)
            for v in connected_component:
                visited[v] = True

    return connected_components

if __name__ == "__main__": g = Graph()

edgeList = [
    (0, 1),
    (0, 3),
    (1, 2),
    (2, 4),
    (2, 5),
    (4, 5),
    (4, 6),
    (4, 7),
    (6, 10),
    (7, 8),
    (7, 10),
    (10, 9),
    (10, 8)
]

for edge in edgeList:
    g.insertEdge(edge)

g.insertVertex(11)
g.sortAdjacencyList()

print("Vertices:", g.vertices())
print("Edges:", g.edges())
print("Size:", g.size)
print("Adjacency List:", g.aList)

print("DFS:", g.DFS(0))
print("BFS:", g.BFS(0))

print("DFS Spanning Tree:", g.DFS_spanning_tree(0))
print("BFS Spanning Tree:", g.BFS_spanning_tree(0))

print("Path from 0 to 10:", g.findPath(0, 10))
print("Cyclic DFS:", g.detectCycleDFS())
print("Connected Components:", g.findConnectedComponents())

print("\n\n")

# list of acyclic graph nodes
edgeList = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 2),
    (3, 4)
]

dag = Graph()
for edge in edgeList:
    dag.insertDirectedEdge(edge)


print("Vertices:", dag.vertices())
print("Edges:", dag.edges())
print("Size:", dag.size)
print("Adjacency List:", dag.aList)

print("DFS:", dag.DFS(1))
print("BFS:", dag.BFS(1))

print("DFS Spanning Tree:", dag.DFS_spanning_tree(1))
print("BFS Spanning Tree:", dag.BFS_spanning_tree(1))

print("Path from 1 to 4:", dag.findPath(1, 4))
print("Cyclic DFS:", dag.detectCycleDFS())
print("Connected Components:", dag.findConnectedComponents())

print("\n\n")

# list of cyclic graph nodes directed
edgeList = [
    (1, 2),
    (2, 5),
    (5, 3),
    (3, 1),
    (3, 2),
    (4, 1),
    (4, 3)
]

cyclic = Graph()
for edge in edgeList:
    cyclic.insertDirectedEdge(edge)

print("Vertices:", cyclic.vertices())
print("Edges:", cyclic.edges())
print("Size:", cyclic.size)
print("Adjacency List:", cyclic.aList)

print("DFS:", cyclic.DFS(1))
print("BFS:", cyclic.BFS(1))

print("DFS Spanning Tree:", cyclic.DFS_spanning_tree(1))
print("BFS Spanning Tree:", cyclic.BFS_spanning_tree(1))

print("Path from 1 to 4:", cyclic.findPath(1, 4))
print("Path from 1 to 5:", cyclic.findPath(1, 5))
print("Cyclic DFS:", cyclic.detectCycleDFS())
print("Connected Components:", cyclic.findConnectedComponents())
//

//PRIMS And Kruskal's class WeightedGraph: def __init__(self): self.aList = {} self.size = 0

def isVertex(self, vertex):
    return vertex in self.aList

def numVertices(self):
    return self.size

def numEdges(self):
    return sum([len(self.aList[vertex]) for vertex in self.aList])

def vertices(self):
    vertices = []
    for vertex in self.aList:
        vertices.append(vertex)
    return vertices

def edges(self):
    edges = []
    for vertex in self.aList:
        for (v, w) in self.aList[vertex]:
            edges.append((vertex, v, w))
    return edges

def insertVertex(self, vertex):
    if not self.isVertex(vertex):
        self.aList[vertex] = []
        self.size += 1
    else:
        print("Vertex already exists")

def insertEdge(self, edge):
    u, v, w = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u] and u not in self.aList[v]:
        self.aList[u].append((v, w))
        self.aList[v].append((u, w))
    else:
        print("Invalid undirected edge")

def insertDirectedEdge(self, edge):
    u, v, w = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u]:
        self.aList[u].append((v, w))
    else:
        print("Invalid directed edge")

def removeVertex(self, vertex):
    if self.isVertex(vertex):
        for v in self.aList[vertex]:
            self.aList[v].remove(vertex)
        self.aList.pop(vertex)
        self.size -= 1
    else:
        print("Vertex does not exist")

def removeEdge(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        if v in self.aList[u]:
            self.aList[u].remove(v)
        if u in self.aList[v]:
            self.aList[v].remove(u)
        else:
            print("Invalid undirected edge")
    else:
        print("Invalid undirected edge")

def mcst_prim(self):
    if len(self.edges()) == 0:
        return None

    visited = {}
    distance = {}
    mst = {}
    for vertex in self.aList:
        visited[vertex] = False
        distance[vertex] = float('inf')
        mst[vertex] = (-1, None)

    picked_v = self.vertices()[0]
    distance[picked_v] = 0

    for i in range(0, self.numVertices()):
        # Get the minimum distance of neighbours
        min_distance = min([distance[v] for v in self.aList if not visited[v]])

        # Find all vertices with that minimum distance that are not visited
        next_vertices = [v for v in self.aList if (not visited[v]) and (distance[v] == min_distance)]

        next_vertex = min(next_vertices)
        visited[next_vertex] = True

        for (v, w) in self.aList[next_vertex]:
            if not visited[v]:
                if w < distance[v]:
                    mst[v] = (next_vertex, w)
                    distance[v] = w

    min_cost = 0
    for vertex in mst:
        if mst[vertex][1] != None:
            min_cost += mst[vertex][1]

    return (mst, min_cost)

def mcst_kruskal(self):
    if len(self.edges()) == 0:
        return None

    # Create a disjoint set for each vertex
    components = {}
    for vertex in self.aList:
        components[vertex] = [vertex]

    mst = {}
    for vertex in self.aList:
        mst[vertex] = (-1, None)

    edgeList = self.edges()

    # Sort by weight
    edgeList.sort(key=lambda x: x[2])

    min_cost = 0
    for (u, v, w) in edgeList:
        # Insert into tree if it does not create a cycle. Try and trace components, you'll understand it's significance - Ashwin
        if components[u] != components[v]:
            # Add edge to mst
            mst[v] = (u, w)
            min_cost += w

            # Assign new component Leader
            new_leader = components[u]
            for vertex in self.aList:
                if components[vertex] == new_leader:
                    components[vertex] = components[v]

    return (mst, min_cost)

edgeList = [('A', 'B', 1), ('A', 'D', 4), ('A', 'E', 3), ('B', 'E', 2), ('E', 'D', 4), ('B', 'D', 4), ('E', 'C', 4), ('E', 'F', 7), ('C', 'F', 5)]

edgeList = [(0,1,10),(0,2,18),(1,2,6),(1,4,20),(2,3,70),(4,5,10),(4,6,10),(5,6,5)]

g = WeightedGraph() for edge in edgeList: g.insertEdge(edge)

print("\n\n") print("Adjacency List:", g.aList)

print("\n\n") print("PRIM'S ALGORITHM") print("Minimum Cost Spanning Tree:", g.mcst_prim()[0]) print("Minimum Cost:", g.mcst_prim()[1])

print("\n\n") print("KRUSKAL'S ALGORITHM") print("Minimum Cost Spanning Tree:", g.mcst_kruskal()[0]) print("Minimum Cost:", g.mcst_kruskal()[1])

//WG

class WeightedGraph: def __init__(self): self.aList = {} self.size = 0

def isVertex(self, vertex):
    return vertex in self.aList

def numVertices(self):
    return self.size

def numEdges(self):
    return sum([len(self.aList[vertex]) for vertex in self.aList])

def sortAdjacencyList(self):
    # Sort keys
    self.aList = dict(sorted(self.aList.items()))
    # Sort values
    for vertex in self.aList:
        self.aList[vertex].sort()

def vertices(self):
    vertices = []
    for vertex in self.aList:
        vertices.append(vertex)
    return vertices

def edges(self):
    edges = []
    for vertex in self.aList:
        for v, w in self.aList[vertex]:
            edges.append((vertex, v, w))
    return edges

def insertVertex(self, vertex):
    if not self.isVertex(vertex):
        self.aList[vertex] = []
        self.size += 1
    else:
        print("Vertex already exists")

def insertEdge(self, edge):
    u, v, w = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u] and u not in self.aList[v]:
        self.aList[u].append((v, w))
        self.aList[v].append((u, w))
    else:
        print("Invalid undirected edge")

def insertDirectedEdge(self, edge):
    u, v, w = edge
    if not self.isVertex(u):
        self.insertVertex(u)
    if not self.isVertex(v):
        self.insertVertex(v)

    if v not in self.aList[u]:
        self.aList[u].append((v, w))
    else:
        print("Invalid directed edge")

def removeVertex(self, vertex):
    if self.isVertex(vertex):
        for v in self.aList[vertex]:
            self.aList[v].remove(vertex)
        self.aList.pop(vertex)
        self.size -= 1
    else:
        print("Vertex does not exist")

def removeEdge(self, edge):
    u, v = edge
    if self.isVertex(u) and self.isVertex(v):
        if v in self.aList[u]:
            self.aList[u].remove(v)
        if u in self.aList[v]:
            self.aList[v].remove(u)
        else:
            print("Invalid undirected edge")
    else:
        print("Invalid undirected edge")

def isDijkstraSafe(self):
    edgeList = self.edges()
    for u, v, w in edgeList:
        if w < 0:
            return False
    return True

# Single Source Shortest path
def dijkstra(self, source):
    if not self.isDijkstraSafe():
        print("Graph is not Dijkstra safe")
        return

    if not self.isVertex(source):
        print("Invalid source vertex")
        return

    visited = {}
    for vertex in self.vertices():
        visited[vertex] = False

    distance = {}
    for vertex in self.vertices():
        distance[vertex] = float("inf")

    distance[source] = 0

    while False in visited.values():
        current_min_node = None
        for vertex in self.vertices():
            if not visited[vertex]:
                if current_min_node is None:
                    current_min_node = vertex
                elif distance[vertex] < distance[current_min_node]:
                    current_min_node = vertex

        for v, w in self.aList[current_min_node]:
            if distance[current_min_node] + w < distance[v]:
                distance[v] = distance[current_min_node] + w

        visited[current_min_node] = True

    return distance

def bellmanFord(self, source):
    if not self.isVertex(source):
        print("Invalid source vertex")
        return

    distance = {}
    predecessor = {}

    for vertex in self.vertices():
        if vertex == source:
            distance[vertex] = 0
        else:
            distance[vertex] = float("inf")
        predecessor[vertex] = None

    for _ in range(self.numVertices() - 1):
        for u, v, w in self.edges():
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                predecessor[v] = u

    for u, v, w in self.edges():
        if distance[u] + w < distance[v]:
            print("Graph contains negative weight cycle")
            return

    return distance, predecessor

# All Pairs Shortest Path
def floydWarshall(self):
    self.sortAdjacencyList()

    n = self.numVertices()
    vertex_to_index = {}
    index_to_vertex = {}

    i = 0
    for vertex in self.vertices():
        vertex_to_index[vertex] = i
        index_to_vertex[i] = vertex
        i += 1

    AMat = [[float("inf") for _ in range(n)] for _ in range(n)]

    for u, v, w in self.edges():
        AMat[vertex_to_index[u]][vertex_to_index[v]] = w

    SP = [[float("inf") for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                SP[i][j] = 0
            else:
                SP[i][j] = AMat[i][j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                SP[i][j] = min(SP[i][j], SP[i][k] + SP[k][j])

    distances = {}
    for v in self.aList:
        distances[v] = {}

    for i in range(n):
        for j in range(n):
            distances[index_to_vertex[i]][index_to_vertex[j]] = SP[i][j]


    return distances

g = WeightedGraph() edgeList = [ (0, 1, 10), (0, 2, 80), (1, 2, 6), (1, 4, 20), (2, 3, 70), (4, 5, 50), (4, 6, 5), (5, 6, 10), ] edgeList = [ (1, 2, 7), (1, 6, 14), (1, 3, 9), (2, 1, 7), (2, 3, 10), (2, 4, 15), (3, 6, 2), (3, 1, 9), (3, 2, 10), (3, 4, 11), (4, 2, 15), (4, 3, 11), (4, 5, 6), (5, 4, 6), (5, 6, 9), (6, 1, 14), (6, 3, 2), (6, 5, 9) ]

for u, v, w in edgeList: g.insertDirectedEdge((u, v, w))

print("\n\n") print("Adjacency List:", g.aList) print("Number of vertices:", g.numVertices()) print("Number of edges:", g.numEdges()) print("Vertices:", g.vertices()) print("Edges:", g.edges())

print("\n") print("Dijkstra:", g.dijkstra(1))

print("\n") print("Bellman-Ford:", g.bellmanFord(1))

print("\n") print("Floyd-Warshall:", g.floydWarshall())

//Sorting //bubble: def bubble_sort(L): if len(L) <= 1: return L

for i in range(len(L)):
    for j in range(len(L)):
        if L[i] < L[j]:
            L[i], L[j] = L[j], L[i]

return L

L = [3, 2, 1, 5, 4] print(bubble_sort(L))

//heap Sort class MinHeap: def __init__(self): self.heap = []

def heapify(self, i):
    l = 2*i + 1
    r = 2*i + 2
    smallest = i

    if l < len(self.heap) and self.heap[l] < self.heap[smallest]:
        smallest = l
    if r < len(self.heap) and self.heap[r] < self.heap[smallest]:
        smallest = r

    if smallest != i:
        self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
        self.heapify(smallest)

def build_heap(self, arr):
    self.heap = arr
    for i in range(len(self.heap) // 2 - 1, -1, -1):
        self.heapify(i)

def insert(self, data):
    self.heap.append(data)
    i = len(self.heap) - 1

    while i > 0:
        parent = (i - 1) // 2
        if self.heap[i] < self.heap[parent]:
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
        else:
            break

def extract_min(self):
    if len(self.heap) == 0:
        return None

    self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
    heap_min = self.heap.pop()
    self.heapify(0)

    return heap_min

def delete(self, data):
    if len(self.heap) == 0:
        return None

    i = self.heap.index(data)
    self.heap[i], self.heap[-1] = self.heap[-1], self.heap[i]
    self.heap.pop()
    self.heapify(i)


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

class MaxHeap: def __init__(self): self.heap = []

def heapify(self, i):
    l = 2*i + 1
    r = 2*i + 2
    largest = i

    if l < len(self.heap) and self.heap[l] > self.heap[largest]:
        largest = l
    if r < len(self.heap) and self.heap[r] > self.heap[largest]:
        largest = r

    if largest != i:
        self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
        self.heapify(largest)

def build_heap(self, arr):
    self.heap = arr
    for i in range(len(self.heap) // 2 - 1, -1, -1):
        self.heapify(i)

def insert(self, data):
    self.heap.append(data)
    i = len(self.heap) - 1

    while i > 0:
        parent = (i - 1) // 2
        if self.heap[i] > self.heap[parent]:
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
        else:
            break

def extract_max(self):
    if len(self.heap) == 0:
        return None

    self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
    heap_max = self.heap.pop()
    self.heapify(0)

    return heap_max

def delete(self, data):
    if len(self.heap) == 0:
        return None

    i = self.heap.index(data)
    self.heap[i], self.heap[-1] = self.heap[-1], self.heap[i]
    self.heap.pop()
    self.heapify(i)


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

def heapSortMin(A): heap = MinHeap() heap.build_heap(A) sorted_arr = [] for _ in range(len(A)): sorted_arr.append(heap.extract_min()) return sorted_arr

def heapSortMax(A): heap = MaxHeap() heap.build_heap(A) sorted_arr = [] for _ in range(len(A)): sorted_arr.append(heap.extract_max()) return sorted_arr

L = [i for i in range(100, 0, -1)] print("Min Heap Sort:", heapSortMin(L))

L = [i for i in range(100, 0, -1)] print("Max Heap Sort:", heapSortMax(L))

//Inertion def insertion_sort(L): if len(L) <= 1: return L

for j in range(1, len(L)):
    key = L[j]
    i = j - 1
    while i >= 0 and L[i] > key:
        L[i + 1] = L[i]
        i -= 1
    L[i + 1] = key

return L

L = [3, 2, 1, 5, 4] print(insertion_sort(L))

//Merge Sort def merge(L, left, mid, right): left_size = mid - left + 1 right_size = right - mid

left_array = [0 for _ in range(left_size)]
right_array = [0 for _ in range(right_size)]

for i in range(left_size):
    left_array[i] = L[left + i]

for i in range(right_size):
    right_array[i] = L[mid + 1 + i]

i = 0
j = 0
k = left

while (i < left_size) and (j < right_size):
    if left_array[i] <= right_array[j]:
        L[k] = left_array[i]
        i += 1
    else:
        L[k] = right_array[j]
        j += 1
    k += 1

while i < left_size:
    L[k] = left_array[i]
    i += 1
    k += 1

while j < right_size:
    L[k] = right_array[j]
    j += 1
    k += 1

def merge_sort(L, left, right): if len(L) <= 1: return L

if left < right:
    mid = (left + right) // 2
    merge_sort(L, left, mid)
    merge_sort(L, mid+1, right)
    merge(L, left, mid, right)

L = [i for i in range(10000, 0, -1)] merge_sort(L, 0, len(L)-1) print(L)

//Quick Sort import random

def quick_sort_extra_space(L): if len(L) <= 1: return L

pivot = random.choice(L)
left = []
right = []
equal = []

for i in L:
    if i < pivot:
        left.append(i)
    elif i > pivot:
        right.append(i)
    else:
        equal.append(i)

return quick_sort_extra_space(left) + equal + quick_sort_extra_space(right)

def partition(L, left, right): pivot_index = random.randint(left, right) pivot = L[pivot_index] L[pivot_index], L[right] = L[right], L[pivot_index]

i = left - 1
for j in range(left, right):
    if L[j] <= pivot:
        i += 1
        L[i], L[j] = L[j], L[i]

L[i+1], L[right] = L[right], L[i+1]

return i + 1

def quick_sort(L, left, right): if left < right: pivot_index = partition(L, left, right) quick_sort(L, left, pivot_index - 1) quick_sort(L, pivot_index + 1, right)

L = [i for i in range(100, 0, -1)]

print("[Extra Space] Before sorting: ", L) print("[Extra Space] After sorting: ", quick_sort_extra_space(L))

print("[In-place] Before sorting: ", L) quick_sort(L, 0, len(L)-1) print("[In-place] After sorting: ", L)

//Selection Sort

def selection_sort(L): if len(L) <= 1: return L

for i in range(len(L)):
    min_index = i
    for j in range(i+1, len(L)):
        if L[min_index] > L[j]:
            min_index = j
    L[i], L[min_index] = L[min_index], L[i]

return L

L = [3, 2, 1, 5, 4] print(selection_sort(L))

//CLL class Node: def __init__(self, data): self.data = data self.next = None self.prev = None

class CircularLinkedList: def __init__(self): self.head = None

def insert_last(self, data):
    newNode = Node(data)

    if self.head is None:
        self.head = newNode
        self.head.next = self.head
        return

    currentNode = self.head
    while currentNode.next != self.head:
        currentNode = currentNode.next

    currentNode.next = newNode
    newNode.next = self.head

def insert_first(self, data):
    newNode = Node(data)

    if self.head is None:
        self.head = newNode
        self.head.next = self.head
        return

    currentNode = self.head
    while currentNode.next != self.head:
        currentNode = currentNode.next

    currentNode.next = newNode
    newNode.next = self.head
    self.head = newNode

def search(self, key):
    if self.head is None:
        return False
    if self.head.data == key:
        return True
    currentNode = self.head.next
    while currentNode != self.head:
        if currentNode.data == key:
            return True
        currentNode = currentNode.next
    return False

def insert_after(self, key, data):
    if self.head is None:
        return False
    if self.head.data == key:
        newNode = Node(data)
        newNode.next = self.head.next
        self.head.next = newNode
        return True
    currentNode = self.head.next
    while currentNode != self.head:
        if currentNode.data == key:
            newNode = Node(data)
            newNode.next = currentNode.next
            currentNode.next = newNode
            return True
        currentNode = currentNode.next
    return False

def insert_before(self, key, data):
    if self.head is None:
        return False
    if self.head.data == key:
        newNode = Node(data)
        newNode.next = self.head
        currentNode = self.head
        while currentNode.next != self.head:
            currentNode = currentNode.next
        currentNode.next = newNode
        self.head = newNode
        return True
    currentNode = self.head
    while currentNode.next != self.head:
        if currentNode.next.data == key:
            newNode = Node(data)
            newNode.next = currentNode.next
            currentNode.next = newNode
            return True
        currentNode = currentNode.next
    return False

def delete(self, key):
    if self.head is None:
        return False
    if self.head.data == key:
        currentNode = self.head
        while currentNode.next != self.head:
            currentNode = currentNode.next
        currentNode.next = self.head.next
        self.head = self.head.next
        return True
    currentNode = self.head
    while currentNode.next != self.head:
        if currentNode.next.data == key:
            currentNode.next = currentNode.next.next
            return True
        currentNode = currentNode.next
    return False

def delete_first(self):
    if self.head is None:
        return False
    if self.head.next == self.head:
        self.head = None
        return True
    currentNode = self.head
    while currentNode.next != self.head:
        currentNode = currentNode.next
    currentNode.next = self.head.next
    self.head = self.head.next
    return True

def delete_last(self):
    if self.head is None:
        return False
    if self.head.next == self.head:
        self.head = None
        return True
    currentNode = self.head
    while currentNode.next.next != self.head:
        currentNode = currentNode.next
    currentNode.next = self.head
    return True

def print_list(self):
    if self.head is None:
        return
    currentNode = self.head
    while True:
        print(currentNode.data, end=" -> ")
        currentNode = currentNode.next
        if currentNode == self.head:
            break
    print()

circularLinkedList = CircularLinkedList() circularLinkedList.insert_last(1) circularLinkedList.insert_last(2) circularLinkedList.insert_last(3) circularLinkedList.insert_last(4) circularLinkedList.insert_last(5) circularLinkedList.insert_last(6) circularLinkedList.insert_last(7)

circularLinkedList.print_list()

circularLinkedList.insert_first(0) circularLinkedList.insert_first(-1) circularLinkedList.insert_first(-2)

circularLinkedList.print_list()

print(circularLinkedList.search(0)) print(circularLinkedList.search(10))

circularLinkedList.insert_after(0, 10) circularLinkedList.insert_after(10, 11)

circularLinkedList.print_list()

circularLinkedList.insert_before(0, -10)

circularLinkedList.print_list()

circularLinkedList.delete(0) circularLinkedList.delete(11) circularLinkedList.delete(10)

circularLinkedList.print_list()

circularLinkedList.delete_first()

circularLinkedList.print_list()

circularLinkedList.delete_last()

circularLinkedList.print_list()

//DLL class Node: def __init__(self, data): self.data = data self.next = None self.prev = None

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

def insert_last(self, data):
    newNode = Node(data)

    if self.head is None:
        self.head = newNode
        self.tail = newNode
        return

    newNode.prev = self.tail
    self.tail.next = newNode
    self.tail = newNode

def insert_first(self, data):
    newNode = Node(data)

    if self.head is None:
        self.head = newNode
        self.tail = newNode
        return

    newNode.next = self.head
    self.head.prev = newNode
    self.head = newNode

def search(self, key):
    currentNode = self.head
    while currentNode:
        if currentNode.data == key:
            return True
        currentNode = currentNode.next
    return False

def insert_after(self, key, data):
    currentNode = self.head
    while currentNode:
        if currentNode.data == key:
            newNode = Node(data)
            newNode.prev = currentNode
            newNode.next = currentNode.next
            currentNode.next = newNode
            if newNode.next:
                newNode.next.prev = newNode
            else:
                self.tail = newNode
            return True
        currentNode = currentNode.next
    return False

def insert_before(self, key, data):
    if self.head is None:
        return False
    if self.head.data == key:
        newNode = Node(data)
        newNode.next = self.head
        self.head.prev = newNode
        self.head = newNode
        return True
    currentNode = self.head
    while currentNode.next:
        if currentNode.next.data == key:
            newNode = Node(data)
            newNode.prev = currentNode
            newNode.next = currentNode.next
            currentNode.next = newNode
            newNode.next.prev = newNode
            return True
        currentNode = currentNode.next
    return False

def delete(self, key):
    if self.head is None:
        return False
    if self.head.data == key:
        self.head = self.head.next
        if self.head:
            self.head.prev = None
        else:
            self.tail = None
        return True
    currentNode = self.head
    while currentNode.next:
        if currentNode.next.data == key:
            currentNode.next = currentNode.next.next
            if currentNode.next:
                currentNode.next.prev = currentNode
            else:
                self.tail = currentNode
            return True
        currentNode = currentNode.next
    return False

def delete_first(self):
    if self.head is None:
        return False
    self.head = self.head.next
    if self.head:
        self.head.prev = None
    else:
        self.tail = None
    return True

def delete_last(self):
    if self.head is None:
        return False
    if self.head == self.tail:
        self.head = None
        self.tail = None
        return True
    self.tail = self.tail.prev
    self.tail.next = None
    return True

def print_list(self):
    if self.head is None:
        print("Empty list")
        return
    currentNode = self.head
    while currentNode:
        print(currentNode.data, end=" -> ")
        currentNode = currentNode.next
    print()

dll = DLL() dll.insert_last(1) dll.insert_last(2) dll.insert_last(3) dll.insert_last(4)

dll.print_list()

dll.insert_first(0) dll.insert_first(-1) dll.insert_first(-2)

dll.print_list()

print(dll.search(0))

dll.insert_after(0, 0.5)

dll.print_list()

dll.insert_before(0, -0.5)

dll.print_list()

dll.delete(0)

dll.print_list()

dll.delete_first()

dll.print_list()

dll.delete_last()

dll.print_list()

dll.delete_last()

dll.print_list()

//SLL

class Node: def __init__(self, data): self.data = data self.next = None

class SLL: def __init__(self): self.head = None

def insert_last(self, data):
    newNode = Node(data)

    if self.head is None:
        self.head = newNode
        return

    currentNode = self.head
    while currentNode.next:
        currentNode = currentNode.next

    currentNode.next = newNode

def insert_first(self, data):
    newNode = Node(data)

    if self.head is None:
        self.head = newNode
        return

    newNode.next = self.head
    self.head = newNode

def search(self, key):
    currentNode = self.head
    while currentNode:
        if currentNode.data == key:
            return True
        currentNode = currentNode.next
    return False

def insert_after(self, key, data):
    currentNode = self.head
    while currentNode:
        if currentNode.data == key:
            newNode = Node(data)
            newNode.next = currentNode.next
            currentNode.next = newNode
            return True
        currentNode = currentNode.next
    return False

def insert_before(self, key, data):
    if self.head is None:
        return False
    if self.head.data == key:
        newNode = Node(data)
        newNode.next = self.head
        self.head = newNode
        return True
    currentNode = self.head
    while currentNode.next:
        if currentNode.next.data == key:
            newNode = Node(data)
            newNode.next = currentNode.next
            currentNode.next = newNode
            return True
        currentNode = currentNode.next
    return False

def delete_nth_occurence(self, key, n):
    currentNode = self.head
    count = 1
    prev = None
    while currentNode:
        if currentNode.data == key:
            if count == n:
                if prev is None:
                    self.head = currentNode.next
                else:
                    prev.next = currentNode.next
                return True
            count += 1
        prev = currentNode
        currentNode = currentNode.next
    return False

def delete_first(self):
    if self.head is None:
        return False
    self.head = self.head.next
    return True

def delete_last(self):
    if self.head is None:
        return False
    if self.head.next is None:
        self.head = None
        return True
    currentNode = self.head
    while currentNode.next.next:
        currentNode = currentNode.next
    currentNode.next = None
    return True

def delete_all_occurences(self, key):
    if self.head is None:
        return False
    while self.head and self.head.data == key:
        self.head = self.head.next
    currentNode = self.head
    while currentNode.next:
        if currentNode.next.data == key:
            currentNode.next = currentNode.next.next
        else:
            currentNode = currentNode.next
    return True

def print_list(self):
    if self.head is None:
        print('List is empty')
        return
    currentNode = self.head
    while currentNode:
        print(currentNode.data, end=" -> ")
        currentNode = currentNode.next
    print()

sll = SLL()

sll.insert_last(1) sll.insert_last(2) sll.insert_last(3) sll.insert_last(4) sll.insert_last(5) sll.insert_last(6) sll.insert_last(7)

sll.insert_first(0) sll.insert_first(0) sll.insert_first(0)

sll.print_list()

print(sll.search(0)) print(sll.search(1)) print(sll.search(2)) print(sll.search(3)) print(sll.search(4))

print(sll.delete_nth_occurence(0, 1)) print(sll.delete_nth_occurence(0, 1)) print(sll.delete_nth_occurence(0, 1))

sll.print_list()

print(sll.delete_first()) print(sll.delete_first()) print(sll.delete_first())

sll.print_list()

print(sll.delete_last()) print(sll.delete_last()) print(sll.delete_last())

sll.print_list()

print(sll.delete_all_occurences(1))

sll.print_list()

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

def enqueue(self, item):
    self.queue.append(item)

def dequeue(self):
    if not self.is_empty():
        return self.queue.pop(0)

    print("Queue is empty")
    return None

def is_empty(self):
    return self.queue == []

def first(self):
    if not self.is_empty():
        return self.queue[0]

    return None

def print_queue(self):
    if not self.is_empty():
        for item in self.queue:
            print(item, end=" ")
        print()
    else:
        print("Queue is empty")

def size(self):
    return len(self.queue)

q = Queue()

q.enqueue(5) q.enqueue(3)

q.print_queue()

q.dequeue()

q.print_queue()

q.enqueue(2) q.enqueue(8)

q.print_queue()

q.dequeue() q.dequeue()

q.print_queue()

print(q.is_empty())

q.enqueue(9) q.enqueue(1)

q.print_queue()

q.dequeue()

q.print_queue()

q.enqueue(7) q.enqueue(6)

q.print_queue()

print(q.first())

q.dequeue() q.dequeue()

q.print_queue()

q.enqueue(4)

q.print_queue()

q.dequeue() q.dequeue()

q.print_queue()

//DEQUE

class Deque: def __init__(self): self.deque = []

def insertFirst(self, item):
    self.deque.insert(0, item)

def insertLast(self, item):
    self.deque.append(item)

def deleteFirst(self):
    if not self.isEmpty():
        return self.deque.pop(0)

    print("Deque is empty")
    return None

def deleteLast(self):
    if not self.isEmpty():
        return self.deque.pop()

    print("Deque is empty")
    return None

def isEmpty(self):
    return self.deque == []

def first(self):
    if not self.isEmpty():
        return self.deque[0]

    return None

def last(self):
    if not self.isEmpty():
        return self.deque[-1]

    return None

def printDeque(self):
    if not self.isEmpty():
        for item in self.deque:
            print(item, end=" ")
        print()
    else:
        print("Deque is empty")

dq = Deque()

//stacks //Expressions

InFix: a + (( b * c ) / d )

PostFix: a b c * d / +

PreFix: + a / * b c d

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

def push(self, item):
    self.stack.append(item)

def pop(self):
    if not self.is_empty():
        return self.stack.pop()

    return None

def is_empty(self):
    return self.stack == []

def peek(self):
    if not self.is_empty():
        return self.stack[-1]

    return None

def top(self):
    if not self.is_empty():
        return self.stack[0]

    return None

def print_stack(self):
    if not self.is_empty():
        for item in self.stack:
            print(item, end=" ")
        print()
    else:
        print("Stack is empty")

def is_operator(c): if c == "+" or c == "-" or c == "*" or c == "/" or c == "^": return True else: return False

def is_operand(c): if c.isalpha() or c.isdigit(): return True else: return False

def precedence(c): if c == "^": return 3 elif c == "*" or c == "/": return 2 elif c == "+" or c == "-": return 1 else: return 0

def infix_to_postfix(infix): postfix = "" stack = Stack()

for c in infix:
    if is_operand(c):
        postfix += c
    elif c == "(":
        stack.push(c)
    elif c == ")":
        while (not stack.is_empty()) and (stack.peek() != "("):
            postfix += stack.pop()
        stack.pop()
    elif is_operator(c):
        while (not stack.is_empty()) and (precedence(c) <= precedence(stack.peek())):
            postfix += stack.pop()
        stack.push(c)

while not stack.is_empty():
    postfix += stack.pop()

return postfix

def infix_to_prefix(infix): prefix = "" stack = Stack()

for c in infix[::-1]:
    if is_operand(c):
        prefix += c
    elif c == ")":
        stack.push(c)
    elif c == "(":
        while (not stack.is_empty()) and (stack.peek() != ")"):
            prefix += stack.pop()
        stack.pop()
    elif is_operator(c):
        while (not stack.is_empty()) and (precedence(c) < precedence(stack.peek())):
            prefix += stack.pop()
        stack.push(c)

while not stack.is_empty():
    prefix += stack.pop()

return prefix[::-1]

def postfix_to_infix(postfix): infix = "" stack = Stack()

for c in postfix:
    if is_operand(c):
        stack.push(c)
    elif is_operator(c):
        op1 = stack.pop()
        op2 = stack.pop()
        stack.push("(" + op2 + c + op1 + ")")

infix = stack.pop()
return infix

def prefix_to_infix(prefix): infix = "" stack = Stack()

for c in prefix[::-1]:
    if is_operand(c):
        stack.push(c)
    elif is_operator(c):
        op1 = stack.pop()
        op2 = stack.pop()
        stack.push("(" + op1 + c + op2 + ")")

infix = stack.pop()
return infix

def prefix_to_postfix(prefix): postfix = "" stack = Stack()

for c in prefix[::-1]:
    if is_operand(c):
        stack.push(c)
    elif is_operator(c):
        op1 = stack.pop()
        op2 = stack.pop()
        stack.push(op1 + op2 + c)

postfix = stack.pop()
return postfix

def postfix_to_prefix(postfix): prefix = "" stack = Stack()

for c in postfix:
    if is_operand(c):
        stack.push(c)
    elif is_operator(c):
        op1 = stack.pop()
        op2 = stack.pop()
        stack.push(c + op2 + op1)

prefix = stack.pop()
return prefix

print() print("[InFix]: a + (( b c ) / d )") print() print("[In -> Post]: ",infix_to_postfix("a+((bc)/d)")) print("[In -> Pre]: ", infix_to_prefix("a+((bc)/d)")) print() print("[Post -> In]: ", postfix_to_infix(infix_to_postfix("a+((bc)/d)"))) print("[Post -> Pre]", postfix_to_prefix(infix_to_postfix("a+((bc)/d)"))) print() print("[Pre -> In]", prefix_to_infix(infix_to_prefix("a+((bc)/d)"))) print("[Pre -> Post]", prefix_to_postfix(infix_to_prefix("a+((b*c)/d)")))

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

def push(self, item):
    self.items.append(item)

def pop(self):
    if not self.is_empty():
        return self.items.pop()

    print("Stack is empty")
    return None

def is_empty(self):
    return self.items == []

def peek(self):
    if not self.is_empty():
        return self.items[-1]

def print_stack(self):
    if not self.is_empty():
        for item in self.items:
            print(item, end=" ")
        print()
    else:
        print("Stack is empty")

st = Stack() st.push(1) st.push(2) st.push(3) st.push(4)

st.print_stack()

st.pop()

st.print_stack()

st.pop() st.pop() st.pop()

st.print_stack()

st.pop()

st.print_stack()