priority queue

A simple implementation of Priority Queue

using Queue.

class PriorityQueue(object): def _init_(self): self.queue = []

def _str_(self):
    return ' '.join([str(i) for i in self.queue])

# for checking if the queue is empty
def isEmpty(self):
    return len(self.queue) == 0

# for inserting an element in the queue
def insert(self, data):
    self.queue.append(data)

# for popping an element based on Priority
def delete(self):
    try:
        max_val = 0
        for i in range(len(self.queue)):
            if self.queue[i] > self.queue[max_val]:
                max_val = i
        item = self.queue[max_val]
        del self.queue[max_val]
        return item
    except IndexError:
        print()
        exit()

if _name_ == '_main_': myQueue = PriorityQueue() myQueue.insert(12) myQueue.insert(1) myQueue.insert(14) myQueue.insert(7) print(myQueue)
while not myQueue.isEmpty(): print(myQueue.delete())

linked list

class Node: def _init_(self,data): self.data = data self.ref = None

class LinkedList: def _init_(self): self.head = None

def print_ll(self):
    if self.head is None:
        print("Linked List is empty")
    else:
        n = self.head
        while n is not None:
            print(n.data)
            n = n.ref

def insert_begin(self,data):
    new_node = Node(data)
    new_node.ref = self.head
    self.head = new_node

def insert_last(self,data):
    new_node = Node(data)
    if self.head is None:
        new_node = self.head
    else:
        n = self.head
        while n.ref is not None:
            n = n.ref
        n.ref = new_node

def insert_after_an_element(self,data,x):
    n = self.head
    while n is not None:
        if n.data == x:
            break;
        else:
            n = n.ref
    if n is None:
        print("Element is not present in the Linked List")
    else:
        new_node = Node(data)
        new_node = n.ref
        n.ref = new_node
def insert_before_an_element(self,data,x):
    if self.head is None:
        print("Linked list is empty")
        return
    if self.head.data == x:
        new_node = Node(data)
        new_node.ref = self.head
        self.head = new_node
        return
    else:
        n = self.data
        while n.ref.ref is not None:
            n = n.ref
        n.ref = new_node

def delete_begin(self):
    if self.head is None:
        print("Linked List is empty")
    else:
        self.head = self.head.ref

def delete_after(self):
    if self.head is None:
        print("Linked List is empty")
    elif self.head.ref is None:
        self.head = None
    else:
        n = self.head
        while n.ref.ref is not None:
            n=n.ref
        n.ref = None

def delete_an_element(self,x):
    if self.head is None:
        print("Linked List is empty")
        return
    if self.head.data == x:
        self.head = self.head.ref
        return
    n = self.head
    while n.ref is not None:
        if n.ref.data == x:
            break;
        else:
            n = n.ref
    if n.ref is None:
        print("Node is not present in the linked list")
    else:
        n.ref = n.ref.ref

list1 = LinkedList() list1.insert_begin(10) list1.insert_begin(20) list1.insert_last(30) list1.insert_last(40) list1.print_ll() list1.delete_begin() list1.print_ll()

double linked list

class Node: def _init_(self,data): self.data = data self.pref = None self.nref = None

class DLinkedList: def _init_(self): self.head = None

def print_forward(self):
    if self.head is None:
        print("Linked List is Empty")
    else:
        n = self.head
        while n is not None:
            print(n.data)
            n = n.nref

def print_backward(self):
    if self.head is None:
        print("Linked List is empty")
    else:
        n = self.head
        while n.nref is not None:
            n = n.nref
        while n is not None:
            print(n.data)
            n = n.pref

def insert_empty(self,data):
    if self.head is None:
        new_node = Node(data)
        self.head = new_node
    else:
        print("Linked List is not empty")

def insert_start(self,data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        new_node.nref = self.head
        self.head.pref = new_node
        self.head = new_node

def insert_end(self,data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        n = self.head
        while n.nref is not None:
            n = n.nref
        n.nref = new_node
        new_node.pref = n

def insert_after(self,data,x):
    if self.head is None:
        print("Linked List is empty")
    else:
        n = self.head
        while n is not None:
            if n.data == x:
                break
            else:
                n = n.nref
        if n is None:
            print("Node is not present in the ll")
        else:
            new_node.nref = n.nref
            new_node.pref = n



def insert_after(self,data,x):
    if self.head is None:
        print("Linked List is empty")
    else:
        n = self.head
        while n is not None:
            n = n.nref
        if n is None:
            print("Node is not present in the linked list")
        else:
            new_node = Node(data)
            new_node.nref = n.nref
            new_node.pref = n
            if n.nref is not None:
                n.pref.nref = new_node
            n.nref = new_node

def insert_before(self,data,x):
    if self.head is None:
        print("Linked List is empty")
    else:
        n = self.head
        while n is not None:
            if n.data == x:
                break
            else:
                n = n.nref
        if n is None:
            print("Node is not present in the ll")
        else:
            new_node = Node(data)
            new_node.nref = n
            new_node.pref = n.pref
            if n.pref is not None:
                n.pref.nref = new_node
            n.pref = new_node


def delete_begin(self):
    if self.head is None:
        print("Linked List is empty")
        return 
    if self.head.nref is None:
        self.head = None
        return
    else:
        self.head = self.head.nref
        self.head.pref = None

def delete_end(self):
    if self.head is None:
        print("Linked List is Empty")
        return
    if self.head.nref is None:
        self.head = None
        return
    else:
        n = self.head
        while n.nref is not None:
            n = n.nref
        n.pref.nref = None

def delete_by_value(self,x):
    if self.head is None:
        print("Linked List is empty")
        return
    if self.head.nref is None:
        if x == self.head.data:
            self.head = None
        else:
            print("Node is not present in the ll")
        return 
    if self.head.data == x:
        self.head = self.head.nref
        self.head.pref = None
        return
    n = self.head
    while n.nref is not None:
        if n.data == x:
            break
        else:
            n = n.nref
    if n.nref is not None:
        n.pref.nref = n.nref
        n.nref.pref = n.pref
    else:
        if x == n.data:
            n.pref.nref = None
        else:
            print("X is not present in the ll")

circular linked list

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

class circularLinkedList:
def _init_(self): self.head = None def add_data(self, my_data): ptr_1 = Node(my_data) temp = self.head
ptr_1.next = self.head

  if self.head is not None:
     while(temp.next != self.head):
        temp = temp.next
     temp.next = ptr_1
  else:
     ptr_1.next = ptr_1
  self.head = ptr_1

def print_it(self): temp = self.head if self.head is not None: while(True): print("%d" %(temp.data)), temp = temp.next if (temp == self.head): break my_list = circularLinkedList() print("Elements are added to the list ") my_list.add_data (56) my_list.add_data (78) my_list.add_data (12) print("The data is : ") my_list.print_it()

implement a stack using queue

Program to implement a stack using

two queue

from _collections import deque

class Stack:

def _init_(self):

    # Two inbuilt queues
    self.q1 = deque()
    self.q2 = deque()

def push(self, x):

    # Push x first in empty q2
    self.q2.append(x)

    # Push all the remaining
    # elements in q1 to q2.
    while (self.q1):
        self.q2.append(self.q1.popleft())

    # swap the names of two queues
    self.q1, self.q2 = self.q2, self.q1

def pop(self):

    # if no elements are there in q1
    if self.q1:
        self.q1.popleft()

def top(self):
    if (self.q1):
        return self.q1[0]
    return None

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

Driver Code

if _name_ == '_main_': s = Stack() s.push(1) s.push(2) s.push(3)

print("current size: ", s.size())
print(s.top())
s.pop()
print(s.top())
s.pop()
print(s.top())

print("current size: ", s.size())

queue using stack

Python3 program to implement Queue using

two stacks with costly enQueue()

class Queue: def _init_(self): self.s1 = [] self.s2 = []

def enQueue(self, x):

    # Move all elements from s1 to s2
    while len(self.s1) != 0:
        self.s2.append(self.s1[-1])
        self.s1.pop()

    # Push item into self.s1
    self.s1.append(x)

    # Push everything back to s1
    while len(self.s2) != 0:
        self.s1.append(self.s2[-1])
        self.s2.pop()

# Dequeue an item from the queue
def deQueue(self):

        # if first stack is empty
    if len(self.s1) == 0:
        print("Q is Empty")

    # Return top of self.s1
    x = self.s1[-1]
    self.s1.pop()
    return x

Driver code

if _name_ == '_main_': q = Queue() q.enQueue(1) q.enQueue(2) q.enQueue(3)

print(q.deQueue())
print(q.deQueue())
print(q.deQueue())

bubble sort

num = int(input("Enter the number = ")) list1 = [int(input()) for x in range(num)]

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

print(list1)

insertion sort

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

Example usage:

my_array = [5, 2, 9, 1, 3] insertion_sort(my_array) print(my_array)

merge sort

def mergesort(list1): if len(list1)>1: mid = len(list1)//2 left_list = list1[:mid] right_list = list1[mid:] mergesort(left_list) mergesort(right_list) i = 0 j = 0 k = 0 while i < len(left_list) and j < len(right_list): if left_list[i] < right_list[j]: list1[k] = left_list[i] i = i + 1 k = k + 1 else: list1[k] = right_list[j] j = j + 1 k = k + 1 while i<len(left_list): list1[k] = left_list[i] i = i + 1 k = k + 1

    while j<len(right_list):
        list1[k] = right_list[j]
        j = j + 1
        k = k + 1

num = int(input("Enter the number of elements = ")) list1 = [int(input()) for x in range(num)]
mergesort(list1) print(list1)

quicksort

def swap(arr,i,j): arr[i],arr[j]=arr[j],arr[i] def partition(arr,l,r): pivot=arr[r] i=l-1 for j in range(l,r,1): if(arr[j]<pivot): i=i+1 swap(arr,i,j) swap(arr,i+1,r) return i+1 def quicksort(arr,l,r): if(l<r): pi=partition(arr,l,r) quicksort(arr,l,pi-1) quicksort(arr,pi+1,r) arr=[5,4,3,2,1] quicksort(arr,0,4) for i in range(5): print(arr[i])

selection sort

num = int(input("Number of elements = ")) list1 = [int(input()) for x in range(num)]

for i in range(len(list1)-1): min_val = min(list1[i:]) min_ind = list1.index(min_val,i) list1[i],list1[min_ind] = list1[min_ind],list1[i] print(list1)

dijkstras algorithm

Python program for Dijkstra's single

source shortest path algorithm. The program is

for adjacency matrix representation of the graph

Library for INT_MAX

import sys

class Graph():

def _init_(self, vertices):
    self.V = vertices
    self.graph = [[0 for column in range(vertices)]
                for row in range(vertices)]

def printSolution(self, dist):
    print("Vertex \tDistance from Source")
    for node in range(self.V):
        print(node, "\t", dist[node])

# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):

    # Initialize minimum distance for next node
    min = sys.maxsize

    # Search not nearest vertex not in the
    # shortest path tree
    for u in range(self.V):
        if dist[u] < min and sptSet[u] == False:
            min = dist[u]
            min_index = u

    return min_index

# Function that implements Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):

    dist = [sys.maxsize] * self.V
    dist[src] = 0
    sptSet = [False] * self.V

    for cout in range(self.V):

        # Pick the minimum distance vertex from
        # the set of vertices not yet processed.
        # x is always equal to src in first iteration
        x = self.minDistance(dist, sptSet)

        # Put the minimum distance vertex in the
        # shortest path tree
        sptSet[x] = True

        # Update dist value of the adjacent vertices
        # of the picked vertex only if the current
        # distance is greater than new distance and
        # the vertex in not in the shortest path tree
        for y in range(self.V):
            if self.graph[x][y] > 0 and sptSet[y] == False and \
                    dist[y] > dist[x] + self.graph[x][y]:
                dist[y] = dist[x] + self.graph[x][y]

    self.printSolution(dist)

Driver's code

if _name_ == "_main_": g = Graph(9) g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0] ]

g.dijkstra(0)

priority queue using heap

Python3 code to implement priority-queue

using array implementation of

binary heap

H = [0]*50 size = -1

Function to return the index of the

parent node of a given node

def parent(i) :

return (i - 1) // 2

Function to return the index of the

left child of the given node

def leftChild(i) :

return ((2 * i) + 1)

Function to return the index of the

right child of the given node

def rightChild(i) :

return ((2 * i) + 2)

Function to shift up the

node in order to maintain

the heap property

def shiftUp(i) :

while (i > 0 and H[parent(i)] < H[i]) :

    # Swap parent and current node
    swap(parent(i), i)

    # Update i to parent of i
    i = parent(i)

Function to shift down the node in

order to maintain the heap property

def shiftDown(i) :

maxIndex = i

# Left Child
l = leftChild(i)

if (l <= size and H[l] > H[maxIndex]) :

    maxIndex = l

# Right Child
r = rightChild(i)

if (r <= size and H[r] > H[maxIndex]) :

    maxIndex = r

# If i not same as maxIndex
if (i != maxIndex) :

    swap(i, maxIndex)
    shiftDown(maxIndex)

Function to insert a

new element in

the Binary Heap

def insert(p) :

global size
size = size + 1
H[size] = p

# Shift Up to maintain
# heap property
shiftUp(size)

Function to extract

the element with

maximum priority

def extractMax() :

global size
result = H[0]

# Replace the value
# at the root with
# the last leaf
H[0] = H[size]
size = size - 1

# Shift down the replaced
# element to maintain the
# heap property
shiftDown(0)
return result

Function to change the priority

of an element

def changePriority(i,p) :

oldp = H[i]
H[i] = p

if (p > oldp) :

    shiftUp(i)

else :

    shiftDown(i)

Function to get value of

the current maximum element

def getMax() :

return H[0]

Function to remove the element

located at given index

def Remove(i) :

H[i] = getMax() + 1

# Shift the node to the root
# of the heap
shiftUp(i)

# Extract the node
extractMax()

def swap(i, j) :

temp = H[i]
H[i] = H[j]
H[j] = temp

Insert the element to the

priority queue

insert(45) insert(20) insert(14) insert(12) insert(31) insert(7) insert(11) insert(13) insert(7)

i = 0

Priority queue before extracting max

print("Priority Queue : ", end = "") while (i <= size) :

print(H[i], end = " ")
i += 1

print()

Node with maximum priority

print("Node with maximum priority :" , extractMax())

Priority queue after extracting max

print("Priority queue after extracting maximum : ", end = "") j = 0 while (j <= size) :

print(H[j], end = " ")
j += 1

print()

Change the priority of element

present at index 2 to 49

changePriority(2, 49) print("Priority queue after priority change : ", end = "") k = 0 while (k <= size) :

print(H[k], end = " ")
k += 1

print()

Remove element at index 3

Remove(3) print("Priority queue after removing the element : ", end = "") l = 0 while (l <= size) :

print(H[l], end = " ")
l += 1

priority queue using linked list

Python3 code to implement Priority Queue

using Singly Linked List

Class to create new node which includes

Node Data, and Node Priority

class PriorityQueueNode:

def _init_(self, value, pr):

self.data = value
self.priority = pr
self.next = None

Implementation of Priority Queue

class PriorityQueue:

def _init_(self):

    self.front = None

# Method to check Priority Queue is Empty
# or not if Empty then it will return True
# Otherwise False
def isEmpty(self):

    return True if self.front == None else False

# Method to add items in Priority Queue
# According to their priority value
def push(self, value, priority):

    # Condition check for checking Priority
    # Queue is empty or not
    if self.isEmpty() == True:

        # Creating a new node and assigning
        # it to class variable
        self.front = PriorityQueueNode(value,
                                    priority)

        # Returning 1 for successful execution
        return 1

    else:

        # Special condition check to see that
        # first node priority value
        if self.front.priority > priority:

            # Creating a new node
            newNode = PriorityQueueNode(value,
                                        priority)

            # Updating the new node next value
            newNode.next = self.front

            # Assigning it to self.front
            self.front = newNode

            # Returning 1 for successful execution
            return 1

        else:

            # Traversing through Queue until it
            # finds the next smaller priority node
            temp = self.front

            while temp.next:

                # If same priority node found then current
                # node will come after previous node
                if priority <= temp.next.priority:
                    break

                temp = temp.next

            newNode = PriorityQueueNode(value,
                                        priority)
            newNode.next = temp.next
            temp.next = newNode

            # Returning 1 for successful execution
            return 1

# Method to remove high priority item
# from the Priority Queue
def pop(self):

    # Condition check for checking
    # Priority Queue is empty or not
    if self.isEmpty() == True:
        return

    else:

        # Removing high priority node from
        # Priority Queue, and updating front
        # with next node
        self.front = self.front.next
        return 1

# Method to return high priority node
# value Not removing it
def peek(self):

    # Condition check for checking Priority
    # Queue is empty or not
    if self.isEmpty() == True:
        return
    else:
        return self.front.data

# Method to Traverse through Priority
# Queue
def traverse(self):

    # Condition check for checking Priority
    # Queue is empty or not
    if self.isEmpty() == True:
        return "Queue is Empty!"
    else:
        temp = self.front
        while temp:
            print(temp.data, end = " ")
            temp = temp.next

Driver code

if _name_ == "_main_":

# Creating an instance of Priority
# Queue, and adding values
# 7 -> 4 -> 5 -> 6
pq = PriorityQueue()
pq.push(4, 1)
pq.push(5, 2)
pq.push(6, 3)
pq.push(7, 0)

# Traversing through Priority Queue
pq.traverse()

# Removing highest Priority item
# for priority queue
pq.pop()

This code is contributed by himanshu kanojiya

prims algorithm

A Python3 program for

Prim's Minimum Spanning Tree (MST) algorithm.

The program is for adjacency matrix

representation of the graph

Library for INT_MAX

import sys

class Graph(): def _init_(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

# A utility function to print
# the constructed MST stored in parent[]
def printMST(self, parent):
    print("Edge \tWeight")
    for i in range(1, self.V):
        print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minKey(self, key, mstSet):

    # Initialize min value
    min = sys.maxsize

    for v in range(self.V):
        if key[v] < min and mstSet[v] == False:
            min = key[v]
            min_index = v

    return min_index

# Function to construct and print MST for a graph
# represented using adjacency matrix representation
def primMST(self):

    # Key values used to pick minimum weight edge in cut
    key = [sys.maxsize] * self.V
    parent = [None] * self.V # Array to store constructed MST
    # Make key 0 so that this vertex is picked as first vertex
    key[0] = 0
    mstSet = [False] * self.V

    parent[0] = -1 # First node is always the root of

    for cout in range(self.V):

        # Pick the minimum distance vertex from
        # the set of vertices not yet processed.
        # u is always equal to src in first iteration
        u = self.minKey(key, mstSet)

        # Put the minimum distance vertex in
        # the shortest path tree
        mstSet[u] = True

        # Update dist value of the adjacent vertices
        # of the picked vertex only if the current
        # distance is greater than new distance and
        # the vertex in not in the shortest path tree
        for v in range(self.V):

            # graph[u][v] is non zero only for adjacent vertices of m
            # mstSet[v] is false for vertices not yet included in MST
            # Update the key only if graph[u][v] is smaller than key[v]
            if self.graph[u][v] > 0 and mstSet[v] == False \
            and key[v] > self.graph[u][v]:
                key[v] = self.graph[u][v]
                parent[v] = u

    self.printMST(parent)

Driver's code

if _name_ == '_main_': g = Graph(5) g.graph = [[0, 2, 0, 6, 0], [2, 0, 3, 8, 5], [0, 3, 0, 0, 7], [6, 8, 0, 0, 9], [0, 5, 7, 9, 0]]

g.primMST()

Contributed by Divyanshu Mehta

kruskal

Python program for Kruskal's algorithm to find

Minimum Spanning Tree of a given connected,

undirected and weighted graph

Class to represent a graph

class Graph:

def _init_(self, vertices):
    self.V = vertices
    self.graph = []

# Function to add an edge to graph
def addEdge(self, u, v, w):
    self.graph.append([u, v, w])

# A utility function to find set of an element i
# (truly uses path compression technique)
def find(self, parent, i):
    if parent[i] != i:

        # Reassignment of node's parent
        # to root node as
        # path compression requires
        parent[i] = self.find(parent, parent[i])
    return parent[i]

# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):

    # Attach smaller rank tree under root of
    # high rank tree (Union by Rank)
    if rank[x] < rank[y]:
        parent[x] = y
    elif rank[x] > rank[y]:
        parent[y] = x

    # If ranks are same, then make one as root
    # and increment its rank by one
    else:
        parent[y] = x
        rank[x] += 1

# The main function to construct MST
# using Kruskal's algorithm
def KruskalMST(self):

    # This will store the resultant MST
    result = []

    # An index variable, used for sorted edges
    i = 0

    # An index variable, used for result[]
    e = 0

    # Sort all the edges in
    # non-decreasing order of their
    # weight
    self.graph = sorted(self.graph,
                        key=lambda item: item[2])

    parent = []
    rank = []

    # Create V subsets with single elements
    for node in range(self.V):
        parent.append(node)
        rank.append(0)

    # Number of edges to be taken is less than to V-1
    while e < self.V - 1:

        # Pick the smallest edge and increment
        # the index for next iteration
        u, v, w = self.graph[i]
        i = i + 1
        x = self.find(parent, u)
        y = self.find(parent, v)

        # If including this edge doesn't
        # cause cycle, then include it in result
        # and increment the index of result
        # for next edge
        if x != y:
            e = e + 1
            result.append([u, v, w])
            self.union(parent, rank, x, y)
        # Else discard the edge

    minimumCost = 0
    print("Edges in the constructed MST")
    for u, v, weight in result:
        minimumCost += weight
        print("%d -- %d == %d" % (u, v, weight))
    print("Minimum Spanning Tree", minimumCost)

Driver code

if _name_ == '_main_': g = Graph(4) g.addEdge(0, 1, 10) g.addEdge(0, 2, 6) g.addEdge(0, 3, 5) g.addEdge(1, 3, 15) g.addEdge(2, 3, 4)

# Function call
g.KruskalMST()

This code is contributed by Neelam Yadav

Improved by James Graça-Jones

boruvkos algorithm

Boruvka's algorithm to find Minimum Spanning

Tree of a given connected, undirected and weighted graph

from collections import defaultdict

Class to represent a graph

class Graph:

def _init_(self,vertices):
    self.V= vertices #No. of vertices
    self.graph = [] # default dictionary to store graph


# function to add an edge to graph
def addEdge(self,u,v,w):
    self.graph.append([u,v,w])

# A utility function to find set of an element i
# (uses path compression technique)
def find(self, parent, i):
    if parent[i] == i:
        return i
    return self.find(parent, parent[i])

# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
    xroot = self.find(parent, x)
    yroot = self.find(parent, y)

    # Attach smaller rank tree under root of high rank tree
    # (Union by Rank)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    #If ranks are same, then make one as root and increment
    # its rank by one
    else :
        parent[yroot] = xroot
        rank[xroot] += 1

# The main function to construct MST using Kruskal's algorithm
def boruvkaMST(self):
    parent = []; rank = [];

    # An array to store index of the cheapest edge of
    # subset. It store [u,v,w] for each component
    cheapest =[]

    # Initially there are V different trees.
    # Finally there will be one tree that will be MST
    numTrees = self.V
    MSTweight = 0

    # Create V subsets with single elements
    for node in range(self.V):
        parent.append(node)
        rank.append(0)
        cheapest =[-1] * self.V

    # Keep combining components (or sets) until all
    # components are not combined into single MST

    while numTrees > 1:

        # Traverse through all edges and update
        # cheapest of every component
        for i in range(len(self.graph)):

            # Find components (or sets) of two corners
            # of current edge
            u,v,w = self.graph[i]
            set1 = self.find(parent, u)
            set2 = self.find(parent ,v)

            # If two corners of current edge belong to
            # same set, ignore current edge. Else check if
            # current edge is closer to previous
            # cheapest edges of set1 and set2
            if set1 != set2:    

                if cheapest[set1] == -1 or cheapest[set1][2] > w :
                    cheapest[set1] = [u,v,w]

                if cheapest[set2] == -1 or cheapest[set2][2] > w :
                    cheapest[set2] = [u,v,w]

        # Consider the above picked cheapest edges and add them
        # to MST
        for node in range(self.V):

            #Check if cheapest for current set exists
            if cheapest[node] != -1:
                u,v,w = cheapest[node]
                set1 = self.find(parent, u)
                set2 = self.find(parent ,v)

                if set1 != set2 :
                    MSTweight += w
                    self.union(parent, rank, set1, set2)
                    print ("Edge %d-%d with weight %d included in MST" % (u,v,w))
                    numTrees = numTrees - 1

        #reset cheapest array
        cheapest =[-1] * self.V


    print ("Weight of MST is %d" % MSTweight)

g = Graph(4) g.addEdge(0, 1, 10) g.addEdge(0, 2, 6) g.addEdge(0, 3, 5) g.addEdge(1, 3, 15) g.addEdge(2, 3, 4)

g.boruvkaMST()

bellmann algorithm

Python3 program for Bellman-Ford's single source

shortest path algorithm.

Class to represent a graph

class Graph:

def _init_(self, vertices):
    self.V = vertices # No. of vertices
    self.graph = []

# function to add an edge to graph
def addEdge(self, u, v, w):
    self.graph.append([u, v, w])

# utility function used to print the solution
def printArr(self, dist):
    print("Vertex Distance from Source")
    for i in range(self.V):
        print("{0}\t\t{1}".format(i, dist[i]))

# The main function that finds shortest distances from src to
# all other vertices using Bellman-Ford algorithm. The function
# also detects negative weight cycle
def BellmanFord(self, src):

    # Step 1: Initialize distances from src to all other vertices
    # as INFINITE
    dist = [float("Inf")] * self.V
    dist[src] = 0

    # Step 2: Relax all edges |V| - 1 times. A simple shortest
    # path from src to any other vertex can have at-most |V| - 1
    # edges
    for _ in range(self.V - 1):
        # Update dist value and parent index of the adjacent vertices of
        # the picked vertex. Consider only those vertices which are still in
        # queue
        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Step 3: check for negative-weight cycles. The above step
    # guarantees shortest distances if graph doesn't contain
    # negative weight cycle. If we get a shorter path, then there
    # is a cycle.

    for u, v, w in self.graph:
        if dist[u] != float("Inf") and dist[u] + w < dist[v]:
            print("Graph contains negative weight cycle")
            return

    # print all distance
    self.printArr(dist)

Driver's code

if _name_ == '_main_': g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3)

# function call
g.BellmanFord(0)

Initially, Contributed by Neelam Yadav

Later On, Edited by Himanshu Garg

floydd warshall

Python3 Program for Floyd Warshall Algorithm

Number of vertices in the graph

V = 4

Define infinity as the large

enough value. This value will be

used for vertices not connected to each other

INF = 99999

Solves all pair shortest path

via Floyd Warshall Algorithm

def floydWarshall(graph): """ dist[][] will be the output matrix that will finally have the shortest distances between every pair of vertices """ """ initializing the solution matrix same as input graph matrix OR we can say that the initial values of shortest distances are based on shortest paths considering no intermediate vertices """

dist = list(map(lambda i: list(map(lambda j: j, i)), graph))

""" Add all vertices one by one
to the set of intermediate
vertices.
---> Before start of an iteration,
we have shortest distances
between all pairs of vertices
such that the shortest
distances consider only the
vertices in the set
{0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of a
iteration, vertex no. k is
added to the set of intermediate
vertices and the
set becomes {0, 1, 2, .. k}
"""
for k in range(V):

    # pick all vertices as source one by one
    for i in range(V):

        # Pick all vertices as destination for the
        # above picked source
        for j in range(V):

            # If vertex k is on the shortest path from
            # i to j, then update the value of dist[i][j]
            dist[i][j] = min(dist[i][j],
                            dist[i][k] + dist[k][j]
                            )
printSolution(dist)

A utility function to print the solution

def printSolution(dist): print("Following matrix shows the shortest distances\ between every pair of vertices") for i in range(V): for j in range(V): if(dist[i][j] == INF): print("%7s" % ("INF"), end=" ") else: print("%7d\t" % (dist[i][j]), end=' ') if j == V-1: print()

Driver's code

if _name_ == "_main_": """ 10 (0)------->(3) | /|\ 5 | | | | 1 |/ | (1)------->(2) 3 """ graph = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1], [INF, INF, INF, 0] ]

# Function call
floydWarshall(graph)

This code is contributed by Mythri J L

circular queue

Circular Queue implementation in Python

class MyCircularQueue():

def _init_(self, k):
    self.k = k
    self.queue = [None] * k
    self.head = self.tail = -1

# Insert an element into the circular queue
def enqueue(self, data):

    if ((self.tail + 1) % self.k == self.head):
        print("The circular queue is full\n")

    elif (self.head == -1):
        self.head = 0
        self.tail = 0
        self.queue[self.tail] = data
    else:
        self.tail = (self.tail + 1) % self.k
        self.queue[self.tail] = data

# Delete an element from the circular queue
def dequeue(self):
    if (self.head == -1):
        print("The circular queue is empty\n")

    elif (self.head == self.tail):
        temp = self.queue[self.head]
        self.head = -1
        self.tail = -1
        return temp
    else:
        temp = self.queue[self.head]
        self.head = (self.head + 1) % self.k
        return temp

def printCQueue(self):
    if(self.head == -1):
        print("No element in the circular queue")

    elif (self.tail >= self.head):
        for i in range(self.head, self.tail + 1):
            print(self.queue[i], end=" ")
        print()
    else:
        for i in range(self.head, self.k):
            print(self.queue[i], end=" ")
        for i in range(0, self.tail + 1):
            print(self.queue[i], end=" ")
        print()

Your MyCircularQueue object will be instantiated and called as such:

obj = MyCircularQueue(5) obj.enqueue(1) obj.enqueue(2) obj.enqueue(3) obj.enqueue(4) obj.enqueue(5) print("Initial queue") obj.printCQueue()

obj.dequeue() print("After removing an element from the queue") obj.printCQueue()

graph circular acyclic

Python program to detect cycle

in a graph

from collections import defaultdict

class Graph(): def _init_(self, vertices): self.graph = defaultdict(list) self.V = vertices

def addEdge(self, u, v):
    self.graph[u].append(v)

def isCyclicUtil(self, v, visited, recStack):

    # Mark current node as visited and
    # adds to recursion stack
    visited[v] = True
    recStack[v] = True

    # Recur for all neighbours
    # if any neighbour is visited and in
    # recStack then graph is cyclic
    for neighbour in self.graph[v]:
        if visited[neighbour] == False:
            if self.isCyclicUtil(neighbour, visited, recStack) == True:
                return True
        elif recStack[neighbour] == True:
            return True

    # The node needs to be popped from
    # recursion stack before function ends
    recStack[v] = False
    return False

# Returns true if graph is cyclic else false
def isCyclic(self):
    visited = [False] * (self.V + 1)
    recStack = [False] * (self.V + 1)
    for node in range(self.V):
        if visited[node] == False:
            if self.isCyclicUtil(node, visited, recStack) == True:
                return True
    return False

Driver code

if _name_ == '_main_': g = Graph(4) g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3)

if g.isCyclic() == 1:
    print("Graph contains cycle")
else:
    print("Graph doesn't contain cycle")

findbst

class TreeNode:

def init(self,value):
    self.left = None
    self.right = None
    self.value = value

def insert(self,value):
    if value < self.value:
        if self.left is None:
            self.left = TreeNode(value)
        else:
            self.left.insert(value)
    else:
        if self.right is None:
            self.right = TreeNode(value)
        else:
            self.right.insert(value)

def preorder_traversal(self):
    print(self.value)
    if self.left:
        self.left.preorder_traversal()
    if self.right:
        self.right.preorder_traversal()

def inorder_traversal(self):
    if self.left:
        self.left.inorder_traversal()
    print(self.value)
    if self.right:
        self.right.inorder_traversal()

def postorder_traversal(self):
    if self.left:
        self.left.postorder_traversal()
    if self.right:
        self.right.postorder_traversal()
    print(self.value)

def find(self,value):
    if value < self.value:
        if self.left is None:
            return False
        else:
            return self.left.find(value)
    elif value > self.value:
        if self.right is None:
            return False
        else:
            self.right.find(value)
    else:
        return True

tree = TreeNode(50) tree.insert(30) tree.insert(20) tree.insert(40) tree.insert(70) tree.insert(60) tree.insert(80)

tree.inorder_traversal() print(tree.find(10))

bstbal

class Node: def init(self, key): self.key = key self.left = None self.right = None

def is_balanced(root): if root is None: return True

left_height = get_height(root.left)
right_height = get_height(root.right)

if abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right):
    return True

return False

def get_height(node): if node is None: return 0

return 1 + max(get_height(node.left), get_height(node.right))

Test case 1: Balanced BST

root = Node(10) root.left = Node(5) root.right = Node(15) root.left.left = Node(2) root.left.right = Node(7)

print("Test case 1:") if is_balanced(root): print("The BST is balanced.") else: print("The BST is not balanced.")

Test case 2: Unbalanced BST

root = Node(10) root.left = Node(5) root.right = Node(15) root.left.left = Node(2) root.left.right = Node(7) root.left.left.left = Node(1)

print("Test case 2:") if is_balanced(root): print("The BST is balanced.") else: print("The BST is not balanced.")

lowcomans

class Node: def init(self, key): self.key = key self.left = None self.right = None

def find_lca(root, node1, node2): if root is None: return None

if root.key > node1.key and root.key > node2.key:
    return find_lca(root.left, node1, node2)
elif root.key < node1.key and root.key < node2.key:
    return find_lca(root.right, node1, node2)
else:
    return root

Create a sample BST

root = Node(10) root.left = Node(5) root.right = Node(15) root.left.left = Node(2) root.left.right = Node(7) root.right.left = Node(12) root.right.right = Node(20)

Find LCA of nodes 2 and 7

node1 = Node(12) node2 = Node(20) lca = find_lca(root, node1, node2) if lca: print("Lowest Common Ancestor of {} and {} is: {}".format(node1.key, node2.key, lca.key)) else: print("Nodes not found or the tree is empty.")

spiraltr

class Tree: def init(self,root=None): self.root=root self.l=[] def spiralOrderTraveral(self,root): if not root: return [] q=[root] ans=[] while q: levels=[] for i in range(len(q)): node=q.pop(0) levels.append(node.val) if node.left: q.append(node.left) if node.left: q.append(node.right) ans.append(levels) for j in range(len(ans)): if j%2==1: lst=ans[j] lst=lst[::-1] ans[j]=lst print("------------") return ans

class TreeNode:
    def init(self,val=None,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

main

bst_root = Tree.TreeNode(50) bst_root.left = Tree.TreeNode(30) bst_root.right = Tree.TreeNode(40) bst_root.left.left = Tree.TreeNode(20) bst_root.left.right = Tree.TreeNode(30) bst_root.right.left = Tree.TreeNode(60) bst_root.right.right = Tree.TreeNode(80)

tree=Tree(bst_root) print(tree.spiralOrderTraveral(bst_root))

deepleftleaf

class Tree: def init(self,root=None): self.root=root self.l=[] def spiralOrderTraveral(self,root): if not root: return [] q=[root] ans=[] while q: levels=[] for i in range(len(q)): node=q.pop(0) levels.append(node.val) if node.left: q.append(node.left) if node.left: q.append(node.right) ans.append(levels)

        return ans[-1][0]

class TreeNode:
    def init(self,val=None,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

bst_root = Tree.TreeNode(50) bst_root.left = Tree.TreeNode(30) bst_root.right = Tree.TreeNode(40) bst_root.left.left = Tree.TreeNode(20) bst_root.left.right = Tree.TreeNode(30) bst_root.right.left = Tree.TreeNode(60) bst_root.right.right = Tree.TreeNode(80)

tree=Tree(bst_root) print(tree.spiralOrderTraveral(bst_root))

binaryheap

class BinaryHeap: def init(self): self.heap = [] self.size = 0

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, index1, index2):
    self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

def insert(self, value):
    self.heap.append(value)
    self.size += 1
    self.heapify_up(self.size - 1)

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

    min_value = self.heap[0]
    self.heap[0] = self.heap[self.size - 1]
    self.heap.pop()
    self.size -= 1
    self.heapify_down(0)

    return min_value

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        self.swap(index, self.parent(index))
        index = self.parent(index)

def heapify_down(self, index):
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < self.size and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < self.size and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def print_heap(self):
    print("Binary Heap:", self.heap)

Usage example

binary_heap = BinaryHeap() binary_heap.insert(4) binary_heap.insert(8) binary_heap.insert(2) binary_heap.insert(10) binary_heap.insert(6)

binary_heap.print_heap() # Output: Binary Heap: [2, 4, 6, 10, 8]

min_value = binary_heap.extract_min() print("Extracted min value:", min_value) # Output: Extracted min value: 2

binary_heap.print_heap() # Output: Binary Heap: [4, 8, 6, 10]

weakheap

class WeakHeap: def init(self): self.heap = [] self.size = 0

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, index1, index2):
    self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

def insert(self, value):
    self.heap.append(value)
    self.size += 1
    self.heapify_up(self.size - 1)

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

    min_value = self.heap[0]
    self.heap[0] = self.heap[self.size - 1]
    self.heap.pop()
    self.size -= 1
    self.heapify_down(0)

    return min_value

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        self.swap(index, self.parent(index))
        index = self.parent(index)

def heapify_down(self, index):
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < self.size and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < self.size and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def merge(self, other_heap):
    self.heap.extend(other_heap.heap)
    self.size += other_heap.size

def print_heap(self):
    print("Weak Heap:", self.heap)

Usage example

heap1 = WeakHeap() heap1.insert(4) heap1.insert(8) heap1.insert(2)

heap2 = WeakHeap() heap2.insert(6) heap2.insert(10)

heap1.print_heap() # Output: Weak Heap: [2, 8, 4] heap2.print_heap() # Output: Weak Heap: [6, 10]

heap1.merge(heap2)

heap1.print_heap() # Output: Weak Heap: [2, 8, 4, 6, 10]

binomialheap

Fibonacci Heap in python

import math

Creating fibonacci tree

class FibonacciTree: def init(self, value): self.value = value self.child = [] self.order = 0

# Adding tree at the end of the tree
def add_at_end(self, t):
    self.child.append(t)
    self.order = self.order + 1

Creating Fibonacci heap

class FibonacciHeap: def init(self): self.trees = [] self.least = None self.count = 0

# Insert a node
def insert_node(self, value):
    new_tree = FibonacciTree(value)
    self.trees.append(new_tree)
    if (self.least is None or value < self.least.value):
        self.least = new_tree
    self.count = self.count + 1

# Get minimum value
def get_min(self):
    if self.least is None:
        return None
    return self.least.value

# Extract the minimum value
def extract_min(self):
    smallest = self.least
    if smallest is not None:
        for child in smallest.child:
            self.trees.append(child)
        self.trees.remove(smallest)
        if self.trees == []:
            self.least = None
        else:
            self.least = self.trees[0]
            self.consolidate()
        self.count = self.count - 1
        return smallest.value

# Consolidate the tree
def consolidate(self):
    aux = (floor_log(self.count) + 1) * [None]

    while self.trees != []:
        x = self.trees[0]
        order = x.order
        self.trees.remove(x)
        while aux[order] is not None:
            y = aux[order]
            if x.value > y.value:
                x, y = y, x
            x.add_at_end(y)
            aux[order] = None
            order = order + 1
        aux[order] = x

    self.least = None
    for k in aux:
        if k is not None:
            self.trees.append(k)
            if (self.least is None
                    or k.value < self.least.value):
                self.least = k

def floor_log(x): return math.frexp(x)[1] - 1

fibonacci_heap = FibonacciHeap()

fibonacci_heap.insert_node(7) fibonacci_heap.insert_node(3) fibonacci_heap.insert_node(17) fibonacci_heap.insert_node(24)

print('the minimum value of the fibonacci heap: {}'.format(fibonacci_heap.get_min()))

print('the minimum value removed: {}'.format(fibonacci_heap.extract_min()))

mirrorbt

class Node: def init(self, value=None): self.leftchild=None self.rightchild=None self.value=value

class BST: def init(self): self.root=None def insert(self, node, value):

    n=Node(value)
    while True:
        if(value>node.value):
            if(node.rightchild is None):
                node.rightchild=n
                break
            else:
                node=node.rightchild
        else:
            if(node.leftchild is None):
                node.leftchild=n
                break
            else:
                node=node.leftchild
def mirror(self, node):
    if not(node) or node.leftchild==None and node.rightchild==None:
        return
    else:
        temp=node.leftchild
        node.leftchild=node.rightchild
        node.rightchild=temp
        if(node.leftchild):
            self.mirror(node.leftchild)
        if(node.rightchild):
            self.mirror(node.rightchild)
    return node
def levelordertraversal(self, node):
    if node==None:
        return []
    ans=[]
    q=[]
    q.append(node)
    ans.append([root.value])
    while q:
        level=[]
        n=len(q)
        for i in range(n):
            curr=q.pop(0)
            if curr.leftchild != None:
                level.append(curr.leftchild.value)
                q.append(curr.leftchild)
            if curr.rightchild != None:
                level.append(curr.rightchild.value)
                q.append(curr.rightchild)
        ans.append(level)
    return(ans[:-1])

root=Node(4) bt=BST() bt.insert(root,2) bt.insert(root,6) bt.insert(root,1) bt.insert(root,3) bt.insert(root,5)

bt.insert(root,7)

print(bt.levelordertraversal(root)) root=bt.mirror(root) print(bt.levelordertraversal(root))

binomaialheap

class BinomialNode: def init(self, key): self.key = key self.degree = 0 self.parent = None self.child = None self.sibling = None

class BinomialHeap: def init(self): self.head = None

def merge(self, heap):
    self.head = self.merge_trees(self.head, heap.head)
    heap.head = None

def merge_trees(self, tree1, tree2):
    if tree1 is None:
        return tree2
    elif tree2 is None:
        return tree1
    else:
        if tree1.key <= tree2.key:
            tree1.sibling = self.merge_trees(tree1.sibling, tree2)
            tree1.parent = tree2
            return tree1
        else:
            tree2.sibling = self.merge_trees(tree1, tree2.sibling)
            tree2.parent = tree1
            return tree2

def insert(self, key):
    temp_heap = BinomialHeap()
    temp_heap.head = BinomialNode(key)
    self.merge(temp_heap)

def get_min(self):
    if self.head is None:
        return None
    min_node = self.head
    current_node = self.head
    while current_node.sibling:
        if current_node.sibling.key < min_node.key:
            min_node = current_node.sibling
        current_node = current_node.sibling
    return min_node.key

def extract_min(self):
    if self.head is None:
        return None
    min_node = self.head
    prev_node = None
    current_node = self.head
    while current_node.sibling:
        if current_node.sibling.key < min_node.key:
            min_node = current_node.sibling
            prev_node = current_node
        current_node = current_node.sibling
    if prev_node:
        prev_node.sibling = min_node.sibling
    else:
        self.head = min_node.sibling
    temp_heap = BinomialHeap()
    temp_heap.head = min_node.child
    temp_heap.reverse()
    self.merge(temp_heap)
    return min_node.key

def reverse(self):
    current_node = self.head
    prev_node = None
    next_node = None
    while current_node:
        next_node = current_node.sibling
        current_node.sibling = prev_node
        prev_node = current_node
        current_node = next_node
    self.head = prev_node

Sample test case

heap = BinomialHeap()

Insertion

heap.insert(8) heap.insert(2) heap.insert(10) heap.insert(5) heap.insert(1)

Extract minimum

print(heap.extract_min()) # Output: 1 print(heap.extract_min()) # Output: 2 print(heap.extract_min()) # Output: 5 print(heap.extract_min()) # Output: 8 print(heap.extract_min()) # Output: 10

leftistheap

class LeftistHeapNode: def init(self, value): self.value = value self.rank = 0 self.left = None self.right = None class LeftistHeap: def init(self): self.root = None

def merge(self, heap1, heap2):
    if heap1 is None:
        return heap2
    if heap2 is None:
        return heap1

    if heap1.value < heap2.value:
        heap1, heap2 = heap2, heap1

    heap1.right = self.merge(heap1.right, heap2)
    if heap1.left is None or heap1.left.rank < heap1.right.rank:
        heap1.left, heap1.right = heap1.right, heap1.left
    if heap1.right is None:
        heap1.rank = 0
    else:
        heap1.rank = heap1.right.rank + 1

    return heap1

def insert(self, value):
    node = LeftistHeapNode(value)
    self.root = self.merge(self.root, node)

def delete_min(self):
    if self.root is None:
        return None

    min_value = self.root.value
    self.root = self.merge(self.root.left, self.root.right)

    return min_value

Example usage:

heap = LeftistHeap() heap.insert(4) heap.insert(2) heap.insert(6) heap.insert(1) heap.insert(8) heap.insert(3)

print(heap.delete_min()) # Output: 1 print(heap.delete_min()) # Output: 2 print(heap.delete_min()) # Output: 3 print(heap.delete_min()) # Output: 4 print(heap.delete_min()) # Output: 6 print(heap.delete_min()) # Output: 8 print(heap.delete_min()) # Output: None (heap is empty)

minheap

class MinHeap: def init(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return 2 * index + 1

def right_child(self, index):
    return 2 * index + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

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

    min_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)
    return min_value

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        self.swap(index, self.parent(index))
        index = self.parent(index)

def heapify_down(self, index):
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)
    if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
        smallest = left
    if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
        smallest = right
    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def get_min(self):
    return self.heap[0] if len(self.heap) > 0 else None

def is_empty(self):
    return len(self.heap) == 0

Example usage:

heap = MinHeap() heap.insert(4) heap.insert(2) heap.insert(6) heap.insert(1) heap.insert(8) heap.insert(3)

print(heap.extract_min()) # Output: 1 print(heap.extract_min()) # Output: 2 print(heap.extract_min()) # Output: 3 print(heap.extract_min()) # Output: 4 print(heap.extract_min()) # Output: 6 print(heap.extract_min()) # Output: 8 print(heap.extract_min()) # Output: None (heap is empty)

maxheap

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

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return 2 * index + 1

def right_child(self, index):
    return 2 * index + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

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

    max_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)
    return max_value

def heapify_up(self, index):
    while index > 0 and self.heap[index] > self.heap[self.parent(index)]:
        self.swap(index, self.parent(index))
        index = self.parent(index)

def heapify_down(self, index):
    largest = index
    left = self.left_child(index)
    right = self.right_child(index)
    if left < len(self.heap) and self.heap[left] > self.heap[largest]:
        largest = left
    if right < len(self.heap) and self.heap[right] > self.heap[largest]:
        largest = right
    if largest != index:
        self.swap(index, largest)
        self.heapify_down(largest)

def get_max(self):
    return self.heap[0] if len(self.heap) > 0 else None

def is_empty(self):
    return len(self.heap) == 0

Example usage:

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

print(heap.extract_max()) # Output: 8 print(heap.extract_max()) # Output: 6 print(heap.extract_max()) # Output: 4 print(heap.extract_max()) # Output: 3 print(heap.extract_max()) # Output: 2 print(heap.extract_max()) # Output: 1 print(heap.extract_max()) # Output: None (heap is empty)

oddlvlnodes

class newNode: def init(self, data): self.data = data self.left = self.right = None

def printOddNodes(root, isOdd = True):

# If empty tree
if (root == None):
    return

# If current node is of odd level
if (isOdd):
    print(root.data, end = " ")

# Recur for children with isOdd
# switched.
printOddNodes(root.left, not isOdd)
printOddNodes(root.right, not isOdd)

Driver code

if name == 'main': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) printOddNodes(root)

exptreefrominfix

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def is_operator(char): return char in ['+', '-', '*', '/']

def construct_expression_tree(infix_expression): stack = [] operators = set(['+', '-', '*', '/']) for char in infix_expression: if char not in operators: node = TreeNode(char) stack.append(node) else: right_node = stack.pop() left_node = stack.pop() operator_node = TreeNode(char) operator_node.left = left_node operator_node.right = right_node stack.append(operator_node)

return stack.pop()

def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.value, end=' ') inorder_traversal(root.right)

Example usage:

infix_expression = "A + B * C - D" root = construct_expression_tree(infix_expression) print("Infix expression:", infix_expression) print("Inorder traversal of the expression tree:") inorder_traversal(root)

heightofbt

class Node:

# Constructor to create a new node
def init(self, data):
    self.data = data
    self.left = None
    self.right = None

def maxDepth(node): if node is None: return 0

else:

    # Compute the depth of each subtree
    lDepth = maxDepth(node.left)
    rDepth = maxDepth(node.right)

    # Use the larger one
    if (lDepth > rDepth):
        return lDepth+1
    else:
        return rDepth+1

Driver program to test above function

root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5)

print("Height of tree is %d" % (maxDepth(root)))

calleafprodnode

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def calculate_leaf_product(root): if root is None: return 1

if root.left is None and root.right is None:
    return root.value

left_product = calculate_leaf_product(root.left)
right_product = calculate_leaf_product(root.right)

return left_product * right_product

def display_leaf_product(root): product = calculate_leaf_product(root) print("Product of leaf nodes:", product)

Example usage:

root = TreeNode(2) root.left = TreeNode(4) root.right = TreeNode(6) root.left.left = TreeNode(3) root.left.right = TreeNode(5) root.right.left = TreeNode(7) root.right.right = TreeNode(9)

display_leaf_product(root)

kthmaxkthmin

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root: inorder_traversal(root.left, values) values.append(root.value) inorder_traversal(root.right, values)

def find_kth_maximum(root, k): values = [] inorder_traversal(root, values) values.sort(reverse=True) if k >= 1 and k <= len(values): return values[k - 1] else: return None

def find_kth_minimum(root, k): values = [] inorder_traversal(root, values) values.sort() if k >= 1 and k <= len(values): return values[k - 1] else: return None

Example usage:

root = TreeNode(4) root.left = TreeNode(2) root.right = TreeNode(6) root.left.left = TreeNode(1) root.left.right = TreeNode(3) root.right.left = TreeNode(5) root.right.right = TreeNode(7)

kth_maximum = find_kth_maximum(root, 3) kth_minimum = find_kth_minimum(root, 2)

print("3rd maximum value:", kth_maximum) # Output: 5 print("2nd minimum value:", kth_minimum) # Output: 2

bst-minh

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, inorder): if root: inorder_traversal(root.left, inorder) inorder.append(root.value) inorder_traversal(root.right, inorder)

def convert_bst_to_binary_tree(root): if root is None: return None

inorder = []
inorder_traversal(root, inorder)

def build_binary_tree(left, right):
    if left > right:
        return None

    mid = (left + right) // 2
    node = TreeNode(inorder[mid])

    node.left = build_binary_tree(left, mid - 1)
    node.right = build_binary_tree(mid + 1, right)

    return node

return build_binary_tree(0, len(inorder) - 1)

def inorder_traversal_print(root): if root: inorder_traversal_print(root.left) print(root.value, end=' ') inorder_traversal_print(root.right)

Example usage:

bst_root = TreeNode(4) bst_root.left = TreeNode(2) bst_root.right = TreeNode(6) bst_root.left.left = TreeNode(1) bst_root.left.right = TreeNode(3) bst_root.right.left = TreeNode(5) bst_root.right.right = TreeNode(7)

binary_tree_root = convert_bst_to_binary_tree(bst_root)

print("Inorder traversal of the BST:") inorder_traversal_print(bst_root) print()

print("Inorder traversal of the converted Binary Tree:") inorder_traversal_print(binary_tree_root) print()

2bst-1tree

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root: inorder_traversal(root.left, values) values.append(root.value) inorder_traversal(root.right, values)

def construct_tree(sorted_values): if not sorted_values: return None

mid = len(sorted_values) // 2
root = TreeNode(sorted_values[mid])

root.left = construct_tree(sorted_values[:mid])
root.right = construct_tree(sorted_values[mid+1:])

return root

def merge_bsts(root1, root2): values = [] inorder_traversal(root1, values) inorder_traversal(root2, values)

values.sort()

return construct_tree(values)

Example usage:

bst1_root = TreeNode(4) bst1_root.left = TreeNode(2) bst1_root.right = TreeNode(6) bst1_root.left.left = TreeNode(1) bst1_root.left.right = TreeNode(3) bst1_root.right.left = TreeNode(5) bst1_root.right.right = TreeNode(7)

bst2_root = TreeNode(9) bst2_root.left = TreeNode(8) bst2_root.right = TreeNode(10)

merged_tree = merge_bsts(bst1_root, bst2_root)

def inorder_traversal_print(root): if root: inorder_traversal_print(root.left) print(root.value, end=' ') inorder_traversal_print(root.right)

print("Inorder traversal of BST1:") inorder_traversal_print(bst1_root) print()

print("Inorder traversal of BST2:") inorder_traversal_print(bst2_root) print()

print("Inorder traversal of the merged tree:") inorder_traversal_print(merged_tree) print()

nonodes

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def count_nodes(root): if root is None: return 0

count = 1
count += count_nodes(root.left)
count += count_nodes(root.right)

return count

Example usage:

root = TreeNode(4) root.left = TreeNode(2) root.right = TreeNode(6) root.left.left = TreeNode(1) root.left.right = TreeNode(3) root.right.left = TreeNode(5) root.right.right = TreeNode(7)

num_nodes = count_nodes(root) print("Number of nodes:", num_nodes)

kpath

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def remove_nodes_greater_than_k(root, k): if root is None: return None

root.left = remove_nodes_greater_than_k(root.left, k)
root.right = remove_nodes_greater_than_k(root.right, k)

if root.left is None and root.right is None:
    if root.value > k:
        return None

return root

def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.value, end=' ') inorder_traversal(root.right)

Example usage:

root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7)

k = 6

print("Before removing nodes:") inorder_traversal(root) print()

root = remove_nodes_greater_than_k(root, k)

print("After removing nodes:") inorder_traversal(root) print()